#include "circuit.h"
#include <vector>
using namespace std;
const int mod=1000002022;
struct T{
int sum,val;
}st[800001];
T operator +(T a, T b){
return {(a.sum+b.sum)%mod,(a.val+b.val)%mod};
}
int n,a[200001],b[200001],lazy[200001],c[200001],id;
vector <int> ke[200001],d[200001];
void down(int node, int l, int r){
if (!lazy[node]||l==r)
return;
st[node<<1].val=(st[node<<1].sum-st[node<<1].val+mod)%mod;
lazy[node<<1]^=1;
st[node<<1|1].val=(st[node<<1|1].sum-st[node<<1|1].val+mod)%mod;
lazy[node<<1|1]^=1;
lazy[node]=0;
}
void build(int node, int l, int r){
if (l==r){
st[node]={b[l],a[l]*b[l]};
return;
}
int mid=(l+r)>>1;
build(node<<1,l,mid);
build(node<<1|1,mid+1,r);
st[node]=st[node<<1]+st[node<<1|1];
}
void update(int node, int l, int r, int u, int v){
if (l>v||r<u)
return;
if (l>=u&&r<=v){
lazy[node]^=1;
st[node].val=(st[node].sum-st[node].val+mod)%mod;
return;
}
down(node,l,r);
int mid=(l+r)>>1;
update(node<<1,l,mid,u,v);
update(node<<1|1,mid+1,r,u,v);
st[node]=st[node<<1]+st[node<<1|1];
}
void dfs(int u){
if (ke[u].empty()){
c[u]=1;
return;
}
c[u]=ke[u].size();
for (int v:ke[u]){
dfs(v);
c[u]=1LL*c[u]*c[v]%mod;
}
}
void dfs2(int u, int val){
if (ke[u].empty()){
b[u]=val;
return;
}
for (int v:ke[u])
d[u].push_back(1LL*(d[u].empty()?1:d[u].back())*c[v]%mod);
int cur=1;
for (int i=ke[u].size()-1;i>=0;i--){
dfs2(ke[u][i],1LL*cur*(i?d[u][i-1]:1)%mod*val%mod);
cur=1LL*cur*c[ke[u][i]]%mod;
}
}
void init(int N, int M, vector <int> P, vector <int> A){
n=N+M;
for (int i=0;i<M;i++)
a[N+i]=A[i];
for (int i=1;i<N+M;i++)
ke[P[i]].push_back(i);
dfs(0);
dfs2(0,1);
build(1,0,n-1);
}
int count_ways(int L, int R){
update(1,0,n-1,L,R);
return st[1].val;
}
