#include "circuit.h"
#include <vector>
#include <bits/stdc++.h>
//#include "stub.cpp"
using namespace std;
typedef long long ll;
const ll mod=1e9+2022;
ll n,m,par[200005];
vector<ll> muchii[200005];
ll val[200005];
ll sub[200005],coef[200005];
void dfs(int nod)
{
sub[nod]=1;
if(muchii[nod].empty())
return;
sub[nod]*=(ll)muchii[nod].size();
sub[nod]%=mod;
for(int i:muchii[nod])
{
dfs(i);
sub[nod]=(sub[nod]*sub[i])%mod;
}
}
void calc(int nod,ll c)
{
if(muchii[nod].empty())
{
coef[nod-n+1]=c;
return;
}
vector<ll> pref;
vector<ll> suf;
ll prod=1;
for(int i=0;i<muchii[nod].size();i++)
{
prod=(prod*sub[muchii[nod][i]])%mod;
pref.push_back(prod);
}
prod=1;
for(int i=(int)muchii[nod].size()-1;i>=0;i--)
{
prod=(prod*sub[muchii[nod][i]])%mod;
suf.push_back(prod);
}
reverse(suf.begin(),suf.end());
for(int i=0;i<muchii[nod].size();i++)
{
ll val=1;
if(i>0)
val=(val*pref[i-1])%mod;
if(i+1<muchii[nod].size())
val=(val*suf[i+1])%mod;
val=(val*c)%mod;
calc(muchii[nod][i],val);
}
}
ll arb[2][8*100005],toprop[8*100005];
void build(int nod,int st,int dr)
{
if(st==dr)
{
arb[0][nod]=(val[st]==0)*coef[st];
arb[1][nod]=(val[st]==1)*coef[st];
return;
}
ll mij=(st+dr)/2;
build(nod*2,st,mij);
build(nod*2+1,mij+1,dr);
arb[0][nod]=(arb[0][nod*2]+arb[0][nod*2+1])%mod;
arb[1][nod]=(arb[1][nod*2]+arb[1][nod*2+1])%mod;
}
void prop(int nod)
{
toprop[nod*2]^=1;
toprop[nod*2+1]^=1;
swap(arb[0][nod*2],arb[1][nod*2]);
swap(arb[0][nod*2+1],arb[1][nod*2+1]);
}
void update(int nod,int st,int dr,int a,int b)
{
if(st!=dr&&toprop[nod])
prop(nod);
toprop[nod]=0;
if(st>=a&&dr<=b)
{
swap(arb[0][nod],arb[1][nod]);
toprop[nod]=1;
return;
}
int mij=(st+dr)/2;
if(a<=mij)
update(nod*2,st,mij,a,b);
if(b>mij)
update(nod*2+1,mij+1,dr,a,b);
arb[0][nod]=(arb[0][nod*2]+arb[0][nod*2+1])%mod;
arb[1][nod]=(arb[1][nod*2]+arb[1][nod*2+1])%mod;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n=N;
m=M;
for(int i=0;i<P.size();i++)
{
muchii[P[i]].push_back(i);
par[i]=P[i];
}
for(int i=0;i<A.size();i++)
val[i+1]=A[i];
dfs(0);
calc(0,1);
build(1,1,m);
}
int count_ways(int L, int R) {
L-=n;
R-=n;
L++;
R++;
update(1,1,m,L,R);
return arb[1][1];
}
