#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef pair<ll, ll> pll;
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a; i >= b; i--)
#define ms memset
#define pb push_back
#define fi first
#define se second
ll MOD = 1e9 + 2022;
int n, m;
vi g[200000];
vector<ll> prod(100000);
vector<ll> b(100000);
vi a;
void get_prod(int u){
prod[u]=max(1,(int)g[u].size());
for (int v : g[u]){
get_prod(v);
prod[u] *= prod[v]; prod[u] %= MOD;
}
}
void dfs(int u, ll val){
int len = g[u].size();
if (len==0){
b[u-n] = val; return;
}
vector<ll> p(len);
FOR(i,0,len){
p[i] = prod[g[u][i]];
}
vector<ll> pre(len+1), suf(len+1);
pre[0]=1; FOR(i,1,len+1){
pre[i]=(pre[i-1]*p[i-1]) % MOD;
}
suf[len]=1; ROF(i,len-1,0){
suf[i]=(suf[i+1]*p[i]) % MOD;
}
FOR(i,0,len){
int v = g[u][i];
ll Val = (pre[i]*suf[i+1]) % MOD;
Val *= val; Val %= MOD;
dfs(v,Val);
}
}
ll ans=0;
void init(int N, int M, vi P, vi A) {
n=N, m=M; a=A;
FOR(i,1,n+m){
g[P[i]].pb(i);
}
get_prod(0); dfs(0,1);
//FOR(i,0,n+m) cout << prod[i] << " ";
//cout << '\n';
//FOR(i,0,m) cout << b[i] << " ";
//cout << '\n';
FOR(i,0,m){
if (a[i]){ans += b[i]; ans %= MOD;}
}
}
int count_ways(int L, int R) {
FOR(i,L-n,R+1-n){
if (a[i]){
ans+=MOD-b[i]; ans %= MOD;
}else{
ans+=b[i]; ans %= MOD;
}
a[i]=1-a[i];
}
return ans;
}
