#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
typedef int ll;
int const Mx = 1e6 + 10;
int n , m , state[Mx] , mod = 1000002022 , dp[Mx] , Size = 1 , val[Mx];
vector<long long>adj[Mx] , off , on , op;
inline long long Mul(long long x , long long y) {
x %= mod;
y %= mod;
return (x * y) % mod;
}
inline long long Add(long long x , long long y) {
x %= mod;
y %= mod;
return (x + y) % mod;
}
struct sgtree {
inline void Init(int n) {
while(Size < n) Size *= 2;
on.assign(Size * 2 , 0);
off.assign(Size * 2 , 0);
op.assign(Size * 2 , 0);
}
inline void Build(int x = 1 , int lx = 1 , int rx = Size) {
if(lx == rx) {
off[x] = val[lx];
return;
}
int mid = (lx + rx) / 2;
Build(2 * x , lx , mid);
Build(2 * x + 1 , mid + 1 , rx);
off[x] = off[2 * x] + off[2 * x + 1];
}
inline void Push(int x) {
if(op[x] == 0) return;
op[x] = 0;
op[2 * x] ^= 1;
op[2 * x + 1] ^= 1;
swap(off[2 * x] , on[2 * x]);
swap(off[2 * x + 1] , on[2 * x + 1]);
}
inline void Update(int l , int r , int x = 1 , int lx = 1 , int rx = Size) {
if(lx > r || rx < l) return;
if(lx >= l && rx <= r) {
swap(off[x] , on[x]);
op[x] ^= 1;
return;
}
Push(x);
int mid = (lx + rx) / 2;
Update(l , r , 2 * x , lx , mid);
Update(l , r , 2 * x + 1 , mid + 1 , rx);
off[x] = off[2 * x] + off[2 * x + 1];
on[x] = on[2 * x] + on[2 * x + 1];
}
}st;
inline void DfsDp(int node) {
dp[node] = 1;
for(auto next : adj[node]) {
DfsDp(next);
dp[node] = Mul(dp[node] , dp[next]);
}
if(adj[node].size()) dp[node] = Mul(dp[node] , adj[node].size());
}
inline void GetVal(int node , int res = 1) {
if(node >= n) {
val[node - n + 1] = res;
return;
}
vector<ll>pref , suf;
for(int i = 0 ; i < adj[node].size() ; ++i) {
int cur = 1 , next = adj[node][i];
if(pref.size()) cur = pref.back();
cur = Mul(cur , dp[next]);
pref.push_back(cur);
}
for(int i = adj[node].size() - 1 ; i >= 0 ; --i) {
int cur = 1 , next = adj[node][i];
if(suf.size()) cur = suf.back();
cur = Mul(cur , dp[next]);
suf.push_back(cur);
}
for(int i = 0 ; i < adj[node].size() ; ++i) {
int CurRes = res , next = adj[node][i];
if(i) CurRes = Mul(CurRes , pref[i - 1]);
if((int)adj[node].size() - i - 2 >= 0) CurRes = Mul(CurRes , suf[adj[node].size() - 2 - i]);
GetVal(next , CurRes);
}
}
void init(int N, int M, vector<ll> P, vector<ll> A) {
n = N , m = M;
for(int i = 1 ; i < P.size() ; ++i) adj[P[i]].push_back(i);
for(int i = 0 ; i < A.size() ; ++i) state[i + 1] = A[i];
DfsDp(0);
GetVal(0);
st.Init(m);
st.Build();
//for(int i = 1 ; i <= m ; ++i) cout << val[i] << " " ;
//cout << endl;
for(int i = 1 ; i <= m ; ++i) if(state[i]) st.Update(i , i);
}
int count_ways(int L , int R) {
L -= n , ++L;
R -= n , ++R;
st.Update(L , R);
return on[1] % mod;
}
