#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define maxn 200005
#define mod 1000002022
struct node{
int s,e,m,lz,on;ll v,sm;
node *l,*r;
node(int _s,int _e){
s=_s;e=_e;m=(s+e)>>1;lz=0;v=0;sm=0;on=0;
if(s!=e)l=new node(s,m),r=new node(m+1,e);
}
void ppo(){
if(lz)v=(sm-v+mod)%mod;
if(s!=e){
l->lz^=lz;
r->lz^=lz;
}
lz=0;
}
void set(int x,ll nv){
if(s==x&&e==x){sm=nv;return;}
if(x<=m)l->set(x,nv);
else r->set(x,nv);
l->ppo(),r->ppo();
v=(l->v+r->v)%mod;
sm=(l->sm+r->sm)%mod;
}
void flip(int x,int y){
if(s==x&&e==y){lz^=1;return;}
if(y<=m)l->flip(x,y);
else if(x>m)r->flip(x,y);
else l->flip(x,m),r->flip(m+1,y);
l->ppo(),r->ppo();
v=(l->v+r->v)%mod;
sm=(l->sm+r->sm)%mod;
}
ll qry(int x,int y){
ppo();
if(s==x&&e==y)return v;
if(y<=m)return l->qry(x,y);
if(x>m)return r->qry(x,y);
return l->qry(x,m),r->qry(m+1,y);
}
}*rt;
int n,m;
ll s[maxn],c[maxn];
vector<int> AL[maxn];
void dfs(int u){
if(u<n){
s[u]=AL[u].size();
for(int v:AL[u]){
dfs(v);
s[u]=(s[u]*s[v])%mod;
}
}
else s[u]=1;
//printf("dfs: %d %lld\n",u,s[u]);
}
void dfs2(int u,ll tot){
//printf("dfs2: %d %lld\n",u,tot);
if(u<n){
vector<ll> vals;
for(int v:AL[u])vals.push_back(s[v]);
vector<ll> pfx={1},sfx={1};
for(int i=0;i<vals.size();++i){
pfx.push_back((pfx.back()*vals[i])%mod);
}
for(int i=vals.size()-1;i>=0;--i){
sfx.push_back((sfx.back()*vals[i])%mod);
}
reverse(sfx.begin(),sfx.end());
for(int i=0;i<vals.size();++i){
dfs2(AL[u][i],(((tot*pfx[i])%mod)*sfx[i+1])%mod);
}
}
else c[u]=tot;
}
void init(int N,int M,vector<int> P,vector<int> A){
n=N,m=M;
rt=new node(0,m-1);
for(int i=1;i<n+m;++i){
AL[P[i]].push_back(i);
}
dfs(0);
dfs2(0,1);
for(int i=0;i<m;++i){
rt->set(i,c[i+n]);
if(A[i])rt->flip(i,i);
}
}
int count_ways(int L, int R){
rt->flip(L-n,R-n);
return (int)rt->qry(0,m-1);
}
