#include "circuit.h"
#include <vector>
typedef long long ll;
using namespace std;
const ll mod=1e9+2022;
struct segtree{
struct DATA{
ll totsum,actsum;
int lz;
DATA(){
totsum=actsum=lz=0;
}
DATA(ll v){
totsum=actsum=v;
lz=0;
}
void apply(){
lz^=1;
}
void flip(){
lz^=1;
actsum=(totsum+mod-actsum)%mod;
}
DATA(DATA a,DATA b){
totsum=a.totsum+b.totsum;
lz=0;actsum=a.actsum+b.actsum;
totsum%=mod,actsum%=mod;
}
} T[1<<20];
void pd(int i){
if(T[i].lz)
T[i].flip(),
T[i*2].apply(),
T[i*2+1].apply();
}
void init(int i,int l,int r,ll arr[]){
if(l==r) return void(T[i]=DATA(arr[l]));
init(i*2,l,l+r>>1,arr);
init(i*2+1,l+r+2>>1,r,arr);
T[i]=DATA(T[i*2],T[i*2+1]);
}
void tog(int i,int l,int r,int ll,int rr){
pd(i); if(ll<=l&&r<=rr)
return T[i].apply(),pd(i);
if(ll>r||l>rr) return;
tog(i*2,l,l+r>>1,ll,rr);
tog(i*2+1,l+r+2>>1,r,ll,rr);
T[i]=DATA(T[i*2],T[i*2+1]);
}
} ST;
vector<int>adj[200100];
ll PRD[200100],FINALE[200100];
void dfs1(int n){
if(adj[n].empty())
return void(PRD[n]=1);
PRD[n]=adj[n].size();
for(auto x:adj[n])
dfs1(x),PRD[n]=PRD[n]*PRD[x]%mod;
}
void dfs2(int n,ll K){
if(adj[n].empty()){
FINALE[n]=K;
}
vector<ll>v1,v2;
v1.push_back(1);
for(auto i:adj[n])
v1.push_back(PRD[i]),
v2.push_back(PRD[i]);
v2.push_back(1);
for(int i=1;i<v1.size();i++)
v1[i]=v1[i-1]*v1[i]%mod;
for(int i=v1.size();--i;)
v2[i-1]=v2[i-1]*v2[i]%mod;
int CC=0;
for(auto i:adj[n]) CC++,
dfs2(i,K*v1[CC-1]%mod*v2[CC]%mod);
}
int N,M;
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++)
adj[P[i]].push_back(i);
dfs1(0);dfs2(0,1);
ST.init(1,N,N+M-1,FINALE);
for(int i=0;i<M;i++)
if(!A[i])
ST.tog(1,0,M-1,i,i);
}
int count_ways(int L, int R) {
ST.tog(1,N,N+M-1,L,R);
return ST.T[1].actsum;
}
