#include"circuit.h"
#include<vector>
#include<iostream>
using namespace std;
typedef long long ll;
const int MOD=1000002022;
const int TREE_SIZE=1<<18;
int parents[200000];
ll sub_mul[200000];
vector<int>children[200000];
int n,m;
ll vals[100000];
struct SegTree{
vector<int>tree;
vector<int>tree_val;
vector<bool>lazy;
void init_tree(int node,int l,int r){
int m=(l+r)/2;
if(m==l)
return;
init_tree(2*node,l,m);
init_tree(2*node+1,m,r);
tree[node]=tree[2*node]+tree[2*node+1];
tree[node]%=MOD;
}
SegTree(ll*arr,int size){
tree.resize(2*TREE_SIZE);
tree_val.resize(2*TREE_SIZE);
lazy.resize(2*TREE_SIZE);
for(int i=0;i<size;i++)
tree[TREE_SIZE+i]=arr[i];
init_tree(1,0,TREE_SIZE);
}
int get(){
return tree_val[1];
}
void push(int node,int l,int r){
if(lazy[node]){
lazy[node]=false;
tree_val[node]=tree[node]+MOD-tree_val[node];
tree_val[node]%=MOD;
if(l<r-1){
lazy[2*node]=!lazy[2*node];
lazy[2*node+1]=!lazy[2*node+1];
}
}
}
void toggle(int node,int rl,int rr,int l,int r){
push(node,l,r);
if(rr<=l||r<=rl)
return;
if(rl<=l&&r<=rr){
lazy[node]=true;
push(node,l,r);
return;
}
int m=(l+r)/2;
toggle(2*node,rl,rr,l,m);
toggle(2*node+1,rl,rr,m,r);
tree_val[node]=tree_val[2*node]+tree_val[2*node+1];
tree_val[node]%=MOD;
}
};
SegTree*segtree;
void dfs2(int node){
if(children[node].empty()){
sub_mul[node]=1;
return;
}
sub_mul[node]=children[node].size();
for(int ch:children[node]){
dfs2(ch);
sub_mul[node]*=sub_mul[ch];
sub_mul[node]%=MOD;
}
}
vector<ll>transform(vector<ll>arr){
if(arr.size()==1)
return {1};
int n=(int)arr.size();
vector<ll>arr1,arr2;
ll arr1_mul=1,arr2_mul=1;
for(int i=0;i<n/2;i++){
arr1.push_back(arr[i]);
arr1_mul*=arr[i];
arr1_mul%=MOD;
}
for(int i=n/2;i<n;i++){
arr2.push_back(arr[i]);
arr2_mul*=arr[i];
arr2_mul%=MOD;
}
vector<ll>res1=transform(arr1),res2=transform(arr2);
vector<ll>res;
for(ll i:res1)
res.push_back((i*arr2_mul)%MOD);
for(ll i:res2)
res.push_back((i*arr1_mul)%MOD);
return res;
}
void dfs3(int node,ll val){
if(children[node].empty()){
vals[node-n]=val;
return;
}
vector<ll>arr(children[node].size());
for(int i=0;i<(int)children[node].size();i++)
arr[i]=sub_mul[children[node][i]];
vector<ll>res=transform(arr);
for(int i=0;i<(int)children[node].size();i++){
ll val2=val*res[i];
val2%=MOD;
dfs3(children[node][i],val2);
}
/*for(int ch:children[node]){
ll val2=val;
for(int ch2:children[node]){
if(ch2!=ch){
val2*=sub_mul[ch2];
val2%=MOD;
}
}
dfs3(ch,val2);
}*/
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n=N;
m=M;
for(int i=0;i<n+m;i++){
parents[i]=P[i];
if(parents[i]!=-1)
children[parents[i]].push_back(i);
}
dfs2(0);
dfs3(0,1);
segtree=new SegTree(vals,m);
for(int i=0;i<(int)A.size();i++)
if(A[i]==1)
segtree->toggle(1,i,i+1,0,TREE_SIZE);
}
int count_ways(int L, int R) {
L-=n;
R-=n;
segtree->toggle(1,L,R+1,0,TREE_SIZE);
/*for(int i=0;i<m;i++)
cout<<active[i]<<" ";
cout<<"\n";
for(int i=0;i<m;i++)
cout<<vals[i]<<" ";
cout<<"\n";*/
return segtree->get();
}
