#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;

#define ff   first
#define ss   second
#define pb   push_back

typedef pair<int,int>   ii;

const int MXN = 4e5+5;
const int mod = 1000002022;

int v[MXN];
int pot[MXN];
vector <int> g[MXN];
int sum0[4*MXN], sum1[4*MXN], lazy[4*MXN];
int subtree[MXN];
int n;
int m;
int a[MXN];

void build (int node, int l, int r) { 
  if (l == r) { 
    if (a[l] == 0) sum0[node] = v[l + n];
    else sum1[node] = v[l + n];
    return;
  }
  int m = (l + r) / 2;
  build (node * 2, l, m);
  build (node * 2 + 1, m + 1, r);
  sum0[node] = (sum0[node * 2] + sum0[node * 2 + 1])%mod;
  sum1[node] = (sum1[node * 2] + sum1[node * 2 + 1])%mod;
 // cout << "in build " << l << ' ' << r << ' ' << sum1[node] << '\n';
}

void propagate (int node) { 
  if (lazy[node]) { 
    swap(sum0[node], sum1[node]);
    lazy[node * 2] ^= 1;
    lazy[node * 2 + 1] ^= 1;
  }
  lazy[node] = 0;
}

void update (int node, int l, int r, int a, int b) {
  propagate(node);
  if (b < l || a > r) return;
  if (a <= l && r <= b) {
    lazy[node] = 1;
    propagate(node);
    return;
  }
  int m = (l + r) / 2;
  update(node * 2, l, m, a, b);
  update(node * 2 + 1, m + 1, r, a, b);
  sum0[node] = (sum0[node * 2] + sum0[node * 2 + 1])%mod;
  sum1[node] = (sum1[node * 2] + sum1[node * 2 + 1])%mod;
}

void dfs (int u) { 
  if (g[u].size()) subtree[u]++;
  for (auto &v : g[u]) { 
    dfs(v);
    subtree[u] += subtree[v];    
  }
}

void init(int N, int M, vector<int> P, vector<int> A) {
  n=N; m=M;
  pot[0]=1;
  for (int i = 1; i < MXN; ++i) pot[i] = (1ll * pot[i - 1] * 2) % mod;
  for (int i = 1; i < N + M; ++i) g[P[i]].pb(i);
  for (int i = 0; i < M; ++i) a[i] = A[i];
  dfs(0);
  v[0]=1;
  for (int i = 1; i < N + M; ++i) { 
    int ot = (g[P[i]][0] == i ? g[P[i]][1] : g[P[i]][0]);
    v[i] = (1ll * v[P[i]] * pot[subtree[ot]]) % mod;
    //cout << i << ' ' << v[i] << '\n';
  }
  build (1, 0, M-1);
}

int count_ways(int L, int R) {
  update(1, 0, m-1, L-n, R-n);
  if (n + m <= 10000) { 
    vector <ii> dp(n + m);
    for (int i = L-n; i <= R-n; ++i) a[i] ^= 1;
    for (int i = n; i < n + m; ++i) dp[i] = {a[i - n],1};
    for (int i = n-1; i >= 0; --i) {
        dp[i].ff = dp[i].ss = 1;
        for (auto &e : g[i]) { 
            ii nw;
            nw.ff = (1ll * dp[i].ff * pot[subtree[e]] + 1ll * dp[i].ss * dp[e].ff) % mod;
            nw.ss = (1ll * dp[i].ss * pot[subtree[e]] + 1ll * dp[i].ff * dp[e].ff) % mod;
            dp[i] = nw;
        }
    }
    return dp[0].ff;
  }
  /*
  vector <int> dp(n + m);
  for (int i = L-n; i <= R-n; ++i) a[i] ^= 1;
  for (int i = n; i < n + m; ++i) dp[i] = a[i - n];
  for (int i = n-1; i >= 0; --i) dp[i] = (1ll * dp[g[i][0]] * pot[subtree[g[i][1]]] + 1ll * dp[g[i][1]] * pot[subtree[g[i][0]]]) % mod;
  cout << dp[0] << '\n';
  cout << sum1[1] << '\n';
  */
  return sum1[1];
}
/*
int main() {
    int N=8,M=9;
    vector <int> P={-1, 0, 0, 1,2,2,3,3,1,6,6,7,7,4,4,5,5};
    vector <int> A={0,0,1,0,0,0,0,0,1};
    init(N,M,P,A);
    count_ways(10,10);
    count_ways(10,10);
    count_ways(9, 14);
    count_ways(13, 16);
    count_ways(8, 12);
    count_ways(9, 14);
    count_ways(9, 11);
    count_ways(10, 12);
    count_ways(9, 14);
    count_ways(9, 14);
    
}
*/