#include "circuit.h"
#include <iostream>
#include <vector>
using namespace std;
const int MAXN=1e5+10;
const long long mod=1e9+2022;
vector <int> v[MAXN];
vector <long long> pref[MAXN], suf[MAXN];
long long mult[MAXN];
long long tree[4*MAXN][2], val[MAXN];
int lazy[MAXN];
int start[MAXN];
int n, m;
void precomp(int x) {
if (v[x].empty()) {
mult[x]=1;
return;
}
pref[x].resize(v[x].size());
suf[x].resize(v[x].size());
mult[x]=v[x].size();
for (int i=0;i<v[x].size();i++) {
precomp(v[x][i]);
if (i==0) pref[x][i]=mult[v[x][i]];
else pref[x][i]=(pref[x][i-1]*mult[v[x][i]])%mod;
mult[x]=(mult[x]*mult[v[x][i]])%mod;
}
for (int i=v[x].size()-1;i>=0;i--) {
if (i==v[x].size()-1) suf[x][i]=mult[v[x][i]];
else suf[x][i]=(suf[x][i+1]*mult[v[x][i]])%mod;
}
}
void dfs(int x, long long ways) {
if (x>=n) {
val[x-n]=ways;
//cout << x << ' ' << ways << endl;
return;
}
long long s;
for (int i=0;i<v[x].size();i++) {
s=1;
if (i>0) s*=pref[x][i-1];
if (i<v[x].size()-1) s*=suf[x][i+1];
s%=mod;
dfs(v[x][i],(ways*s)%mod);
}
}
void build_tree(int node, int l, int r) {
if (l==r) {
tree[node][0]=tree[node][1]=0;
tree[node][start[l]]=val[l];
return;
}
int mid=(l+r)/2;
build_tree(node*2,l,mid);
build_tree(node*2+1,mid+1,r);
tree[node][0]=(tree[node*2][0]+tree[node*2+1][0])%mod;
tree[node][1]=(tree[node*2][1]+tree[node*2+1][1])%mod;
}
void push_lazy(int node, int l, int r) {
if (l!=r && lazy[node]%2==1) {
lazy[node*2]++;
lazy[node*2+1]++;
swap(tree[node*2][0],tree[node*2][1]);
swap(tree[node*2+1][0],tree[node*2+1][1]);
}
lazy[node]=0;
}
void update(int node, int l, int r, int ql, int qr) {
if (ql>r || qr<l) return;
push_lazy(node,l,r);
if (l>=ql && r<=qr) {
swap(tree[node][0],tree[node][1]);
lazy[node]++;
return;
}
int mid=(l+r)/2;
update(node*2,l,mid,ql,qr);
update(node*2+1,mid+1,r,ql,qr);
tree[node][0]=(tree[node*2][0]+tree[node*2+1][0])%mod;
tree[node][1]=(tree[node*2][1]+tree[node*2+1][1])%mod;
}
void init(int N, int M, vector <int> p, vector <int> a) {
n=N;
m=M;
for (int i=1;i<n+m;i++) v[p[i]].push_back(i);
for (int i=0;i<m;i++) start[i]=a[i];
precomp(0);
dfs(0,1);
build_tree(1,0,m-1);
}
int count_ways(int l, int r) {
l-=n; r-=n;
update(1,0,m-1,l,r);
return tree[1][1];
}
