#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 1000002022;
struct segTree{
vector<pair<ll, ll>> v;
vector<int> upd;
int sz;
void init(int n){
sz = 1;
while(sz < n) sz *= 2;
v.assign(2 * sz, {0, 0});
upd.assign(2 * sz, 0);
}
void set(int i, pair<ll, ll> p, int x, int lx, int rx){
if(rx - lx == 1){
v[x] = p;
return;
}
int m = (lx + rx) / 2;
if(i < m) set(i, p, 2 * x + 1, lx, m);
else set(i, p, 2 * x + 2, m, rx);
v[x].first = (v[2 * x + 1].first + v[2 * x + 2].first) % MOD;
v[x].second = (v[2 * x + 1].second + v[2 * x + 2].second) % MOD;
}
void set(int i, pair<ll, ll> p){
set(i, p, 0, 0, sz);
}
void push(int x){
if(upd[x]){
upd[2 * x + 1] ^= 1;
swap(v[2 * x + 1].first, v[2 * x + 1].second);
upd[2 * x + 2] ^= 1;
swap(v[2 * x + 2].first, v[2 * x + 2].second);
upd[x] = 0;
}
}
void change(int l, int r, int x, int lx, int rx){
if(lx >= l && rx <= r){
swap(v[x].first, v[x].second);
upd[x] ^= 1;
return;
}else if(lx >= r || rx <= l) return;
int m = (lx + rx) / 2;
push(x);
change(l, r, 2 * x + 1, lx, m);
change(l, r, 2 * x + 2, m, rx);
v[x].first = (v[2 * x + 1].first + v[2 * x + 2].first) % MOD;
v[x].second = (v[2 * x + 1].second + v[2 * x + 2].second) % MOD;
}
void change(int l, int r){
change(l, r, 0, 0, sz);
}
};
void getSub(int x, vector<vector<int>>& adj, vector<ll>& subtree){
ll opt = (int)adj[x].size();
subtree[x] = opt;
for(int node : adj[x]){
getSub(node, adj, subtree);
if(!adj[node].empty()){
subtree[x] *= subtree[node];
subtree[x] %= MOD;
}
}
// cout << "x " << x << " subtree " << subtree[x] << endl;
}
void DFS(int x, vector<vector<int>>& adj, vector<ll>& subtree, vector<ll>& dp, ll curr = 1){
int sz = (int)adj[x].size();
dp[x] = curr;
if(!sz) return;
vector<ll> suf(sz+1, 1);
for(int i = sz - 1; i >= 0; i--){
suf[i] = suf[i+1] * max(subtree[adj[x][i]], 1ll);
suf[i] %= MOD;
}
ll nw = 1;
for(int i = 0; i < sz; i++){
ll all = nw * suf[i+1]; all %= MOD;
DFS(adj[x][i], adj, subtree, dp, (curr * all) % MOD);
nw *= max(subtree[adj[x][i]], 1ll); nw %= MOD;
}
}
segTree st;
void init(int N, int M, vector<int> P, vector<int> A) {
vector<vector<int>> adj(N+M);
for(int i = 1; i < N + M; i++){
adj[P[i]].push_back(i);
}
vector<ll> subtree(N+M);
getSub(0, adj, subtree);
vector<ll> dp(N+M, 0);
DFS(0, adj, subtree, dp);
st.init(N+M);
for(int i = N; i < N+M; i++){
// cout << "i " << i << " dp " << dp[i] << "\n";
pair<ll, ll> p = {dp[i], 0};
if(!A[i-N]) swap(p.first, p.second);
st.set(i, p);
}
}
int count_ways(int L, int R) {
st.change(L, R + 1);
return st.v[0].first;
}
// int n;
// vector<vector<int>> Adj;
// vector<int> A;
// pair<ll, ll> getAns(int x){
// int sz = (int)Adj[x].size();
// if(!sz){
// if(A[x-n]) return {1, 0};
// else return {0, 1};
// }
// vector<ll> ways(sz + 1, 0); ways[0] = 1;
// for(int node : Adj[x]){
// pair<ll, ll> w = getAns(node);
// for(int i = sz; i >= 0; i--){
// if(i+1 <= sz) ways[i+1] = (ways[i+1] + ways[i] * w.first) % MOD;
// ways[i] = (ways[i] * w.second) % MOD;
// }
// }
// // cout << "x " << x << endl;
// // for(int y : ways) cout << y << " ";
// // cout << endl;
// vector<ll> suf(sz+1, 0), pre(sz + 1, 0);
// pre[0] = ways[0];
// for(int i = 1; i <= sz; i++) pre[i] = (pre[i-1] + ways[i]) % MOD;
// suf[sz] = ways[sz];
// for(int i = sz - 1; i >= 0; i--) suf[i] = (suf[i+1] + ways[i]) % MOD;
// ll good = 0, bad = 0;
// for(int c = 1; c <= sz; c++){
// good += suf[c];
// bad += pre[c-1];
// good %= MOD; bad %= MOD;
// }
// // cout << "x " << x << " good " << good << " bad " << bad << "\n";
// return {good, bad};
// }
// void init2(int N, int M, vector<int> P, vector<int> _A) {
// n = N;
// Adj.clear();
// Adj.resize(N+M);
// for(int i = 1; i < N + M; i++){
// Adj[P[i]].push_back(i);
// }
// A = _A;
// }
// int count_ways2(int L, int R) {
// for(int i = L-n; i <= R-n; i++) A[i] ^= 1;
// return (int)(getAns(0).first);
// }
// mt19937 gen(time(0));
// void eras(vector<int>& lft, int elem){
// vector<int> nw;
// for(int x : lft){
// if(x != elem) nw.push_back(x);
// }
// lft = nw;
// }
// int main(){
// for(int h = 0; h < 10000; h++){
// int N = gen() % 5 + 1;
// int M = gen() % 5 + N;
// vector<int> P(N+M);
// P[0] = -1;
// vector<int> lft(N);
// for(int i = 0; i < N; i++) lft[i] = i;
// for(int i = 1; i < N; i++){
// P[i] = gen() % min(i, N);
// eras(lft, P[i]);
// }
// for(int i = 0; i < M; i++){
// if(lft.empty()) P[i+N] = gen() % N;
// else{
// int ind = gen() % (int)(lft.size());
// P[i+N] = lft[ind];
// eras(lft, P[i+N]);
// }
// }
// vector<int> A(M);
// for(int i = 0; i < M; i++){
// A[i] = gen() % 2;
// }
// init(N, M, P, A);
// init2(N, M, P, A);
// vector<pair<int, int>> queries;
// int Q = gen() % 2 + 1;
// bool bad = false;
// while(Q--){
// int R = gen() % M + 1;
// int L = gen() % R + 1;
// L--; R--; L += N; R += N;
// queries.push_back({L, R});
// if(count_ways(L, R) != count_ways2(L, R)){
// bad = true;
// break;
// }
// }
// if(bad){
// cout << N << " " << M << " " << (int)queries.size() << endl;
// for(int x : P) cout << x << " "; cout << endl;
// for(int x : A) cout << x << " "; cout << endl;
// for(pair<int, int> p : queries) cout << p.first << " " << p.second << endl;
// return 0;
// }
// }
// }
