#include "circuit.h"
// #include "stub.cpp"
#include <bits/stdc++.h>
#define MOD 1000002022
using namespace std;
struct SEG{
private:
struct Node{
long long sum,val;
bool flip;
Node(){}
Node(long long isum){
sum = isum,flip = false,val = 0;
}
};
vector<Node> tree;
vector<long long> mul;
int N;
void init(int l,int r,int idx){
if(l == r){
tree[idx] = Node(mul[l]);
return;
}
int m = (l+r)/2;
init(l,m,idx*2);
init(m+1,r,idx*2+1);
tree[idx] = Node((tree[idx*2].sum+tree[idx*2+1].sum)%MOD);
}
void flip(int l,int r,int idx,int L,int R){
if(l == L && r == R){
tree[idx].val = (tree[idx].sum-tree[idx].val+MOD)%MOD;
tree[idx].flip = !tree[idx].flip;
return;
}
// push tag down
if(tree[idx].flip){
tree[idx*2].val = (tree[idx*2].sum-tree[idx*2].val+MOD)%MOD;
tree[idx*2+1].val = (tree[idx*2+1].sum-tree[idx*2+1].val+MOD)%MOD;
tree[idx*2].flip = !tree[idx*2].flip;
tree[idx*2+1].flip = !tree[idx*2+1].flip;
tree[idx].flip = false;
}
int m = (l+r)/2;
if(R <= m){
flip(l,m,idx*2,L,R);
}else if(L >= m+1){
flip(m+1,r,idx*2+1,L,R);
}else{
flip(l,m,idx*2,L,m);
flip(m+1,r,idx*2+1,m+1,R);
}
tree[idx].val = (tree[idx*2].val+tree[idx*2+1].val)%MOD;// only val change;
}
public:
SEG(){}
SEG(vector<long long> imul){
mul = imul;
N = mul.size();
tree.resize(4*N+5);
init(0,N-1,1);
}
long long getAns(){
return tree[1].val;
}
void flip(int l,int r){
flip(0,N-1,1,l,r);
}
};
vector<vector<int>> child;
vector<long long> tot;
vector<long long> mul;
int N,M;
vector<int> A;
SEG seg;
void init(int iN, int iM, vector<int> P, vector<int> iA) {
N = iN,M = iM;
A = iA;
child.resize(N);
for(int i = 1;i < P.size();i++){
child[P[i]].push_back(i);
}
tot = vector<long long>(N+M,1);
for(int i = N-1;i >= 0;i--){
tot[i] = child[i].size();
for(auto c:child[i]){
tot[i] = tot[i]*tot[c]%MOD;
}
}
mul.resize(M);
function<void(int,long long)> dfs = [&](int cur,long long cval){
if(cur >= N){
mul[cur-N] = cval;
return;
}
if(child[cur].size() == 2){
dfs(child[cur][0],cval*tot[child[cur][1]]%MOD);
dfs(child[cur][1],cval*tot[child[cur][0]]%MOD);
return;
}
vector<long long> suf;
for(auto nxt:child[cur]){
suf.push_back(tot[nxt]);
}
for(int i = suf.size()-2;i >= 0;i--) suf[i] = suf[i]*suf[i+1]%MOD;
long long pref = 1;
for(int i = 0;i < child[cur].size();i++){
int nxt = child[cur][i];
if(i+1 < child[cur].size()) dfs(nxt,cval*pref%MOD*suf[i+1]%MOD);
else dfs(nxt,cval*pref%MOD);
pref = pref*tot[nxt]%MOD;
}
};
dfs(0,1LL);
seg = SEG(mul);
for(int i = 0;i < M;i++) if(A[i]) seg.flip(i,i);
}
int count_ways(int L, int R) {
L -= N, R -= N;
seg.flip(L,R);
return seg.getAns();
}
/*
62: precalculate size, multiply it, range flip
*/
