#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod=1000002022;
const int MAXN=200005;
int n;
long long dp[MAXN];
vector<int> gr[MAXN];
void dfs(int v)
{
int brs=gr[v].size();
dp[v]=brs;
if(!brs) dp[v]=1;
for(int i=0; i<brs; i++)
{
dfs(gr[v][i]);
dp[v]*=dp[gr[v][i]];
dp[v]%=mod;
}
}
long long tole[MAXN], tori[MAXN];
long long coef[MAXN];
void dfs_hp(int v)
{
int brs=gr[v].size();
if(!brs) return;
if(brs==1)
{
coef[gr[v][0]]=1;
dfs_hp(gr[v][0]);
return;
}
tole[0]=dp[gr[v][0]];
for(int i=1; i<brs; i++)
{
tole[i]=tole[i-1]*dp[gr[v][i]]%mod;
}
tori[brs-1]=dp[gr[v][brs-1]];
for(int i=brs-2; i>=0; i--)
{
tori[i]=tori[i+1]*dp[gr[v][i]]%mod;
}
coef[gr[v][0]]=tori[1];
coef[gr[v][brs-1]]=tole[brs-2];
for(int i=1; i<brs-1; i++)
{
coef[gr[v][i]]=tole[i-1]*tori[i+1]%mod;
}
for(int i=0; i<brs; i++) dfs_hp(gr[v][i]);
}
long long pozv[MAXN];
long long st[MAXN];
void dfs_final(int v)
{
int brs=gr[v].size();
for(int i=0; i<brs; i++)
{
st[gr[v][i]]*=st[v];
st[gr[v][i]]%=mod;
dfs_final(gr[v][i]);
}
}
long long pref[MAXN];
long long sums[4*MAXN];
long long segm_v[4*MAXN];
int lazy[4*MAXN];
void build_tree(int v, int le, int ri)
{
if(le==ri)
{
sums[v]=pref[le];
if(le) sums[v]-=pref[le-1];
return;
}
int mid=(le+ri)/2;
build_tree(2*v, le, mid);
build_tree(2*v+1, mid+1, ri);
sums[v]=sums[2*v]+sums[2*v+1];
}
void push_lazy(int v, int le, int ri)
{
if(!lazy[v]) return;
lazy[v]=0;
segm_v[v]=sums[v]-segm_v[v];
if(le!=ri)
{
lazy[2*v]^=1;
lazy[2*v+1]^=1;
}
}
void update_tree(int v, int le, int ri, int be, int en)
{
push_lazy(v, le, ri);
if(le>en || ri<be) return;
if(be<=le && ri<=en)
{
lazy[v]=1;
push_lazy(v, le, ri);
return;
}
int mid=(le+ri)/2;
update_tree(2*v, le, mid, be, en);
update_tree(2*v+1, mid+1, ri, be, en);
segm_v[v]=segm_v[2*v]+segm_v[2*v+1];
}
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
n=N+M;
for(int i=1; i<N+M; i++)
{
gr[P[i]].push_back(i);
}
dfs(0);
dfs_hp(0);
coef[0]=1;
for(int i=0; i<N+M; i++) st[i]=coef[i];
dfs_final(0);
pref[0]=st[0];
for(int i=1; i<n; i++) pref[i]=pref[i-1]+st[i];
build_tree(1, 0, n-1);
for(int i=0; i<M; i++)
{
if(A[i]) update_tree(1, 0, n-1, N+i, N+i);
}
}
int count_ways(int L, int R)
{
update_tree(1, 0, n-1, L, R);
return segm_v[1]%mod;
}
