#include "circuit.h"
#include <vector>
const int MOD = 1000002022;
using namespace std;
struct node {
long long s, x = 1;
vector<node*> l;
};
void dfs(node* n){
if(n->l.empty()){
n->s = 1;
}else n->s = n->l.size();
for(node* c : n->l){
dfs(c);
n->s = n->s*c->s%MOD;
}
}
void dfx(node* n){
if(n->l.empty()) return;
long long x = n->x;
for(node* c : n->l){
c->x = c->x*x%MOD;
x = (x*c->s)%MOD;
}
x = 1;
for(int i = n->l.size()-1;i >= 0;i--){
node*c = n->l[i];
c->x = c->x * x %MOD;
x = (x*c->s)%MOD;
dfx(c);
}
}
const int nx = 4e5+10;
int st[nx], su[nx];bool lz[nx] = {false};
int n;
int cons(int i, int l, int r, const vector<int>& A, node g[]){
if(l==r){
if(A[l-n]) st[i] = g[l].x;
else st[i]=0;
su[i]=g[l].x;
return st[i];
}
int m = l+r>>1;
st[i] = (cons(i<<1, l, m, A, g)+cons(i<<1|1, m+1, r, A, g))%MOD;
su[i] = (su[i<<1]+su[i<<1|1])%MOD;
return st[i];
}
void upd(int i, int l, int r, int a, int b){
if(lz[i]){
st[i] = (su[i]-st[i]+MOD)%MOD;
if(l!=r){
lz[i<<1] ^= 1;
lz[i<<1|1] ^= 1;
}
lz[i]=false;
}
if(b < l || r < a) return;
if(a <= l && r <= b){
st[i] = (su[i]-st[i]+MOD)%MOD;
if(l!=r){
lz[i<<1] ^= 1;
lz[i<<1|1] ^= 1;
}
return;
}
int m = l+r>>1;
upd(i<<1, l, m, a, b);upd(i<<1|1, m+1, r, a, b);
st[i] = (st[i<<1]+st[i<<1|1])%MOD;
}
int nm;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
node g[N+M];
nm = N+M-1;
n = N;
for(int i = 1;i < N+M;i++){
g[P[i]].l.push_back(&g[i]);
}
dfs(&g[0]);
dfx(&g[0]);
cons(1, N, N+M-1, A, g);
}
int count_ways(int L, int R) {
upd(1, n, nm, L, R);
return st[1];
}
