#include "circuit.h"
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
#define all(a) (a).begin(), (a).end()
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int maxn = 2e5 + 5;
const int MOD = 1000002022;
int mult(ll x, ll y) {return x * y % MOD;}
int add(int x, int y) {x += y;if(x >= MOD) x -= MOD;return x;}
int n, m;
int c[maxn];
int prod[maxn];
vector<int> adj[maxn];
vector<int> pref[maxn], suff[maxn];
struct Seg {
int pot;
vector<ii> T;
vector<int> L;
void init(int sz) {
pot = 1;
while(pot < sz) pot <<= 1;
for(int i = 0;i < (pot << 1);i++) T.pb({0, 0}), L.pb(0);
for(int i = 0;i < m;i++)
T[i + pot] = {0, c[i]};
for(int i = pot - 1;i > 0;i--) {
T[i].x = add(T[i * 2].x, T[i * 2 + 1].x);
T[i].y = add(T[i * 2].y, T[i * 2 + 1].y);
}
}
void prop(int x) {
if(L[x] == 0) return;
swap(T[x].x, T[x].y);
if(x < pot)
L[x * 2] ^= 1, L[x * 2 + 1] ^= 1;
L[x] = 0;
}
void update(int x, int lo, int hi, int a, int b) {
prop(x);
if(hi < a || b < lo) return;
if(a <= lo && hi <= b) {
L[x] ^= 1;
prop(x);
return;
}
int mid = (lo + hi) / 2;
update(x * 2, lo, mid, a, b);
update(x * 2 + 1, mid + 1, hi, a, b);
T[x].x = add(T[x * 2].x, T[x * 2 + 1].x);
T[x].y = add(T[x * 2].y, T[x * 2 + 1].y);
}
void toggle(int lo, int hi) {update(1, 0, pot - 1, lo, hi);}
int get() {return T[1].x;}
} S;
void dfs(int x) {
prod[x] = (int)adj[x].size();
for(int y : adj[x]) dfs(y);
for(int y : adj[x]) {
int p = 1;
if(pref[x].size()) p = pref[x].back();
pref[x].pb(mult(p, prod[y]));
}
reverse(all(adj[x]));
for(int y : adj[x]) {
int p = 1;
if(suff[x].size()) p = suff[x].back();
suff[x].pb(mult(p, prod[y]));
}
reverse(all(suff[x]));
reverse(all(adj[x]));
if(pref[x].size())
prod[x] = mult(prod[x], pref[x].back());
if(adj[x].size() == 0)
prod[x] = 1;
}
void solve(int x, int sol) {
if(x >= n) c[x - n] = sol;
int i = 0;
for(int y : adj[x]) {
int l = 1;
if(i) l = pref[x][i - 1];
int r = 1;
if(i < (int)adj[x].size() - 1) r = suff[x][i + 1];
solve(y, mult(sol, mult(l, r)));
i++;
}
}
void init(int N, int M, vector<int> P, vector<int> A) {
n = N, m = M;
for(int i = 1;i < n + m;i++)
adj[P[i]].pb(i);
dfs(0);
solve(0, 1);
S.init(m);
for(int i = 0;i < m;i++)
if(A[i]) S.toggle(i, i);
}
int count_ways(int L, int R) {
L -= n, R -= n;
S.toggle(L, R);
return S.get();
}
