#include "circuit.h"
#include <bits/stdc++.h>
#include <vector>
#define MAXN 200007
#define MOD 1000002022
using namespace std;
vector<int> g[MAXN];
long long a[MAXN],t[MAXN],seg[2][4*MAXN];
int n,m,p[MAXN],st[MAXN],bag[4*MAXN];
void dfst(int s)
{
for(int i=0;i<g[s].size();i++) dfst(g[s][i]);
if(g[s].size()==0) t[s]=1;
else t[s]=g[s].size();
for(int i=0;i<g[s].size();i++) t[s]=(t[s]*t[g[s][i]])%MOD;
}
void dfs(int s,long long p)
{
if(s>=n) {a[s-n]=p%MOD; return;}
vector<long long> lv(g[s].size()+7),ds(g[s].size()+7);
ds[0]=1; lv[g[s].size()+1]=1;
for(int i=0;i<g[s].size();i++) ds[i+1]=(ds[i]*t[g[s][i]])%MOD;
for(int i=g[s].size()-1;i>=0;i--) lv[i+1]=(lv[i+2]*t[g[s][i]])%MOD;
for(int i=0;i<g[s].size();i++) dfs(g[s][i],(p*((ds[i]*lv[i+2])%MOD))%MOD);
}
void build(int l,int r,int ind)
{
if(l==r) {seg[st[l]][ind]=a[l]; return;}
int s=(l+r)/2;
build(l,s,2*ind);
build(s+1,r,2*ind+1);
for(int k=0;k<2;k++) seg[k][ind]=(seg[k][2*ind]+seg[k][2*ind+1])%MOD;
}
void relax(int ind)
{
bag[2*ind]^=bag[ind]; bag[2*ind+1]^=bag[ind];
bag[ind]=0;
}
void upd(int lt,int rt,int l,int r,int ind)
{
if(r<lt || l>rt) return;
if(l>=lt && r<=rt) {bag[ind]^=1; return;}
relax(ind);
int s=(l+r)/2;
upd(lt,rt,l,s,2*ind);
upd(lt,rt,s+1,r,2*ind+1);
for(int k=0;k<2;k++) seg[k][ind]=(seg[k^bag[2*ind]][2*ind]+seg[k^bag[2*ind+1]][2*ind+1])%MOD;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n=N; m=M;
for(int i=1;i<N+M;i++) g[P[i]].push_back(i);
for(int i=0;i<M;i++) st[i]=A[i];
dfst(0); dfs(0,1);
build(0,m-1,1);
}
int count_ways(int L, int R) {
upd(L-n,R-n,0,m-1,1);
return seg[1^bag[1]][1];
}
