#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
const ll maxn = 200005;
basic_string<ll> edges[maxn];
ll sub[maxn];
ll realsub[maxn];
ll par[maxn];
ll prod[maxn];
ll prefs[maxn];
ll pos[maxn];
vector<ll> pref[maxn], suff[maxn];
void dfs(ll a){
prod[a] = 1;
for (auto&i : edges[a]){
dfs(i);
prod[a] *= prod[i];
prod[a] %= 1000002022;
pref[a].push_back(prod[a]);
}
reverse(edges[a].begin(), edges[a].end());
ll temp = 1;
for (auto&i : edges[a]){
temp *= prod[i];
temp %= 1000002022;
suff[a].push_back(temp);
}
reverse(suff[a].begin(), suff[a].end());
reverse(edges[a].begin(), edges[a].end());
if ( edges[a].size() != 0) prod[a] *= edges[a].size();
prod[a] %= 1000002022;
}
ll cache[maxn];
ll dp(ll a){
if (cache[a] != -1) return cache[a];
if (a==0) return 1;
cache[a] = dp(par[a]);
if (pos[a] != 1) cache[a] *= pref[par[a]][pos[a]-2];
cache[a] %= 1000002022;
if (pos[a] != suff[par[a]].size()) cache[a] *= suff[par[a]][pos[a]];
cache[a] %= 1000002022;
return cache[a] %= 1000002022;
}
ll states[maxn];
ll vals[maxn];
ll ans = 0;
ll n;
ll tree[maxn*4];
ll lazy[maxn*4];
ll calc(ll k, ll x, ll y){
if (lazy[k]%2==1){
return prefs[y] - prefs[x] + vals[x] - tree[k];
}else{
return tree[k];
}
}
void push(ll k, ll x, ll y){
lazy[k*2] += lazy[k];
lazy[k*2+1] += lazy[k];
tree[k] = prefs[y] - prefs[x] + vals[x] - tree[k];
lazy[k] = 0;
}
void update(ll a, ll b, ll k=1, ll x =0, ll y = n-1){
if (y<a || b<x) return;
if (a<=x && y<=b){
lazy[k]++;
return;
}
push(k,x,y);
ll mid = (x+y)/2;
update(a,b,k*2,x,mid);
update(a,b,k*2+1,mid+1,y);
tree[k] = calc(k*2,x,mid) + calc(k*2+1, mid+1, y);
}
void sets(ll a, ll b, ll val, ll k=1, ll x =0, ll y = n-1){
if (y<a || b<x) return;
if (a<=x && y<=b){
tree[k] = val;
return;
}
ll mid = (x+y)/2;
sets(a,b,val,k*2,x,mid);
sets(a,b,val,k*2+1,mid+1,y);
tree[k] = calc(k*2,x,mid) + calc(k*2+1, mid+1, y);
}
ll query(ll a, ll b, ll k=1, ll x =0, ll y = n-1){
if (y<a || b<x) return 0;
if (a<=x && y<=b){
return calc(k,x,y);
}
push(k,x,y);
ll mid = (x+y)/2;
return query(a,b,k*2,x,mid) + query(a,b,k*2+1,mid+1,y);
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N+M;
FOR(i,0,maxn) cache[i] = -1, prefs[i] = 0;
FOR(i,0,4*maxn) tree[i] = 0, lazy[i] = 0;
par[0] = -1;
FOR(i,1,N+M){
edges[P[i]].push_back(i);
pos[i] = edges[P[i]].size();
par[i] = P[i];
}
dfs(0);
FOR(i,0,M){
vals[N+i] = dp(N+i);
sets(N+i, N+i, vals[N+i]);
}
FOR(i,0,N) prefs[i] = 0;
FOR(i,N,N+M){
prefs[i] = prefs[i-1] + vals[i];
}
FOR(i,0,M){
if (A[i] == 0) update(N+i,N+i);
}
}
int count_ways(int L, int R) {
update(L, R);
return (query(0,n-1)+1000002022)%1000002022;
}
