#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long
#define sz(s) (int)s.size()
#define pb push_back
using namespace std;
const int MAX=2e5+10;
const int mod=1000002022;
int n,m;
vector<int> a;
vector<int> g[MAX];
int c[MAX];
struct segtree{
int t[4*MAX],s[4*MAX],add[4*MAX];
void build(int v,int tl,int tr){
add[v]=0;
if(tl==tr){
t[v]=a[tl]*c[tl];
s[v]=c[tl];
return;
}
int tm=(tl+tr)/2;
build(2*v,tl,tm);
build(2*v+1,tm+1,tr);
t[v]=(t[2*v]+t[2*v+1])%mod;
s[v]=(s[2*v]+s[2*v+1])%mod;
}
void upd(int v){
add[v]^=1;
t[v]=(s[v]-t[v]+mod)%mod;
}
void push(int v){
if(add[v]){
upd(2*v);
upd(2*v+1);
add[v]=0;
}
}
void update(int v,int tl,int tr,int l,int r){
if(l>r||tl>r||l>tr)return;
if(l<=tl&&tr<=r){
upd(v);
return;
}
int tm=(tl+tr)/2;
push(v);
update(2*v,tl,tm,l,r);
update(2*v+1,tm+1,tr,l,r);
t[v]=(t[2*v]+t[2*v+1])%mod;
s[v]=(s[2*v]+s[2*v+1])%mod;
}
}T;
int pr[MAX];
void calc(int v){
pr[v]=sz(g[v]);
if(g[v].empty())pr[v]=1;
for(auto to:g[v]){
calc(to);
pr[v]=pr[v]*1ll*pr[to]%mod;
}
}
void dfs(int v,int s){
if(g[v].empty()){
c[v-n]=s;
return;
}
vector<int> pref(sz(g[v]),0),suf(sz(g[v]),0);
pref[0]=pr[g[v][0]];
for(int i=1;i<sz(g[v]);i++){
pref[i]=pref[i-1]*1ll*pr[g[v][i]]%mod;
}
suf[sz(g[v])-1]=pr[g[v][sz(g[v])-1]];
for(int i=sz(g[v])-2;i>=0;i--){
suf[i]=suf[i+1]*1ll*pr[g[v][i]]%mod;
}
for(int i=0;i<sz(g[v]);i++){
int to=g[v][i];
int f=s*1ll*(i-1>=0?pref[i-1]:1)%mod*(i+1<sz(g[v])?suf[i+1]:1)%mod;
dfs(to,f);
}
}
void init(int N, int M,vector<int> P,vector<int> A) {
n=N;
m=M;
a=A;
for(int i=1;i<N+M;i++){
g[P[i]].pb(i);
}
calc(0);
dfs(0,1);
T.build(1,0,M-1);
}
int count_ways(int L, int R){
L-=n;
R-=n;
// cout<<L<<" "<<R<<"\n";
T.update(1,0,m-1,L,R);
return T.t[1];
}
