#include<bits/stdc++.h>
#define MAXN 800007
using namespace std;
const long long mod=1000002022;
int n,m,maxdep,pw;
long long st[MAXN],total,diff,zeros,ans,a[MAXN];
long long pref[MAXN],pr,sz[MAXN];
vector<long long> v[MAXN],prefs[MAXN],suffs[MAXN];
long long power(long long x,int y){
if(y==0)return 1;
if(y==1)return x;
if(y==2)return (x*x)%mod;
if(y%2==0)return power(power(x,y/2),2);
return (power(power(x,y/2),2)*x)%mod;
}
void calc(int x){
if(v[x].size()==0){
sz[x]=1; return;
}
sz[x]=int(v[x].size());
prefs[x].resize(v[x].size());
suffs[x].resize(v[x].size());
for(int i=0;i<v[x].size();i++){
calc(v[x][i]);
sz[x]*=sz[v[x][i]];
sz[x]%=mod;
prefs[x][i]=sz[v[x][i]];
if(i>0)prefs[x][i]*=prefs[x][i-1];
prefs[x][i]%=mod;
}
for(int i=v[x].size()-1;i>=0;i--){
suffs[x][i]=sz[v[x][i]];
if(i<v[x].size()-1)suffs[x][i]*=suffs[x][i+1];
suffs[x][i]%=mod;
}
}
void dfs(int x,long long curr){
if(v[x].size()==0){
st[x]=curr;
return;
}
long long t;
for(int i=0;i<v[x].size();i++){
if(v[x].size()==1){
t=1;
}else if(i==0){
t=suffs[x][i+1];
}else if(i==v[x].size()-1){
t=prefs[x][i-1];
}else{
t=(prefs[x][i-1]*suffs[x][i+1])%mod;
}
dfs(v[x][i],(curr*t)%mod);
}
}
long long tree[MAXN],lazy[MAXN];
long long sum(int l,int r){
if(l==0)return pref[r];
return (pref[r]-pref[l-1]+mod)%mod;
}
void psh(int v,int l,int r){
if(lazy[v]==0)return;
int tt=(l+r)/2;
tree[2*v]=(sum(l,tt)-tree[2*v]+mod)%mod;
lazy[2*v]^=1;
tree[2*v+1]=(sum(tt+1,r)-tree[2*v+1]+mod)%mod;
lazy[2*v+1]^=1;
lazy[v]=0;
}
void update(int v,int l,int r,int ll,int rr){
if(ll>rr)return;
if(l==ll and r==rr){
tree[v]=(sum(l,r)-tree[v]+mod)%mod;
lazy[v]^=1;
}else{
int tt=(l+r)/2;
psh(v,l,r);
update(2*v,l,tt,ll,min(tt,rr));
update(2*v+1,tt+1,r,max(tt+1,ll),rr);
tree[v]=(tree[2*v]+tree[2*v+1])%mod;
}
}
void init(int N, int M,vector<int> P,vector<int> A){
n=N; m=M;
for(int i=1;i<N+M;i++){
v[P[i]].push_back(i);
}
calc(0);
dfs(0,1);
for(int i=0;i<m;i++){
pref[i]=st[i+N];
if(i>0)pref[i]+=pref[i-1];
pref[i]%=mod;
}
for(int i=0;i<m;i++){
if(A[i]==1)update(1,0,m-1,i,i);
}
}
int count_ways(int L, int R){
L-=n; R-=n;
update(1,0,m-1,L,R);
return tree[1];
}
/*
int main(){
init(3,4, {-1,0,1,1,2,2,0}, {0,0,0,0});
cout<<count_ways(3,6)<<"\n";
}
*/
