#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
int n,m;
long long mod=1e9+2022;
struct node{
long long sum=0,sga=0,lazy=0;
};
vector<vector<int>>g;
vector<long long>tot,klk,crnoilbelo;
vector<node>st;
void dfs(int a,int b,long long sum)
{
if(a>=n)
{
klk[a-n]=sum;
return;
}
vector<long long>suf(g[a].size());
long long pref=1;
for(int i=suf.size()-1;i>=0;i--)
{
suf[i]=(tot[g[a][i]]*pref)%mod;
pref=pref*tot[g[a][i]]%mod;
}
pref=1;
for(int i=0;i<g[a].size();i++)
{
if(i==g[a].size()-1)dfs(g[a][i],a,(sum*pref)%mod);
else
{
dfs(g[a][i],a,sum*pref%mod*suf[i+1]%mod);
}
pref=pref*tot[g[a][i]]%mod;
}
}
void build(int i,int l,int r)
{
if(l==r)
{
st[i].sum=klk[l];
if(crnoilbelo[l]==1)st[i].sga=klk[l];
return;
}
int m1=(l+r)/2;
build(2*i,l,m1);
build(2*i+1,m1+1,r);
st[i].sum=(st[2*i].sum+st[2*i+1].sum)%mod;
st[i].sga=(st[2*i].sga+st[2*i+1].sga)%mod;
}
void update(int i,int l,int r,int tl,int tr)
{
if(st[i].lazy==1)
{
st[i].sga=(st[i].sum-st[i].sga+mod)%mod;
st[i].lazy=0;
if(l!=r)
{
st[2*i].lazy^=1;
st[2*i+1].lazy^=1;
}
}
if(l>r||tl>r||l>tr)return;
if(tl<=l&&r<=tr)
{
st[i].sga=(st[i].sum-st[i].sga+mod)%mod;
if(l!=r)
{
st[2*i].lazy^=1;
st[2*i+1].lazy^=1;
}
return;
}
int m1=(l+r)/2;
update(2*i,l,m1,tl,tr);
update(2*i+1,m1+1,r,tl,tr);
st[i].sga=(st[2*i].sga+st[2*i+1].sga)%mod;
}
void init(int N, int M,vector<int> P,vector<int> A) {
n=N;m=M;
for(auto i:A)crnoilbelo.push_back(i);
g.resize(n);
klk.resize(m);
for(int i=1;i<P.size();i++)
{
g[P[i]].push_back(i);
}
tot.resize(n+m,1);
for(int i=n-1;i>=0;i--)
{
for(auto j:g[i])
{
tot[i]=(tot[i]*tot[j])%mod;
}
tot[i]=(tot[i]*g[i].size())%mod;
}
dfs(0,0,1);
st.resize(4*m+1);
build(1,0,m-1);
}
int count_ways(int L, int R) {
update(1,0,m-1,L-n,R-n);
return st[1].sga;
}
