#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[400000];
vector<ll> prod(200000);
vector<ll> b(200000);
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;
struct segtree{
int sz; vi neg; vector<ll> sm;
void build(int v, int tl, int tr){
if (tl==tr){
if (a[tl]==0) sm[v]=MOD-b[tl];
else sm[v]=b[tl];
return;
}
int tm = (tl+tr)/2;
build(2*v,tl,tm); build(2*v+1,tm+1,tr);
sm[v]=(sm[2*v]+sm[2*v+1]) % MOD;
}
void init(int n){
sz=n; neg.assign(4*n,1); sm.assign(4*n,0);
build(1,0,sz-1);
}
void update(int v, int tl, int tr, int l, int r){
if (tl != tr && neg[v]==-1){
neg[2*v]=-neg[2*v]; sm[2*v]=MOD-sm[2*v];
neg[2*v+1]=-neg[2*v+1]; sm[2*v+1]=MOD-sm[2*v+1];
neg[v]=1;
}
if (tl==l && tr==r){
neg[v]=-neg[v]; sm[v]=MOD-sm[v]; return;
}
if (l>r) return;
int tm = (tl+tr)/2;
update(2*v,tl,tm,l,min(r,tm)); update(2*v+1,tm+1,tr,max(l,tm+1),r);
sm[v]=(sm[2*v]+sm[2*v+1]) % MOD;
}
void update(int l, int r){update(1,0,sz-1,l,r);}
ll get(int v, int tl, int tr, int l, int r){
if (tl != tr && neg[v]==-1){
neg[2*v]=-neg[2*v]; sm[2*v]=MOD-sm[2*v];
neg[2*v+1]=-neg[2*v+1]; sm[2*v+1]=MOD-sm[2*v+1];
neg[v]=1;
}
if (tl==l && tr==r) return sm[v];
if (l>r) return 0;
int tm = (tl+tr)/2;
ll val = (get(2*v,tl,tm,l,min(r,tm))+get(2*v+1,tm+1,tr,max(l,tm+1),r)) % MOD;
sm[v]=(sm[2*v]+sm[2*v+1])%MOD;
return val;
}
ll get(int l, int r){return get(1,0,sz-1,l,r);}
};
segtree st;
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,m) cout << a[i] << " ";
//cout << '\n';
//FOR(i,0,m) cout << b[i] << " ";
//cout << '\n';
st.init(m);
FOR(i,0,m){
if (a[i]){ans += b[i]; ans %= MOD;}
}
}
int count_ways(int L, int R) {
st.update(L-n,R-n);
//FOR(i,0,m) cout << st.get(i,i) << " ";
//cout << '\n';
ans += st.get(L-n,R-n);
ans %= MOD;
return ans;
}
