#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1000002022;
const int MN = 1e5+5;
int n, m;
vector<vector<int>> tree;
vector<ll> contrib, w;
vector<int> state;
ll ans = 0;
void calc_w(int node) {
w[node] = tree[node].size();
if (tree[node].empty()) w[node] = 1;
for (auto next: tree[node]) {
calc_w(next);
w[node] = (w[node] * w[next]) % MOD;
}
}
void calc_c(int node) {
vector<int> todo;
for (auto next: tree[node]) todo.push_back(next);
int c = todo.size();
if (c == 0) return;
vector<ll> pref(c, 0), suff(c, 0);
pref[0] = w[todo[0]];
for (int i = 1; i < c; i++) {
pref[i] = pref[i-1] * w[todo[i]] % MOD;
}
suff[c-1] = w[todo[c-1]];
for (int i = c-2; i >= 0; i--) {
suff[i] = suff[i+1] * w[todo[i]] % MOD;
}
for (int i = 0; i < c; i++) {
contrib[todo[i]] = 1;
if (i > 0) contrib[todo[i]] = (contrib[todo[i]] * pref[i-1]) % MOD;
if (i < c-1) contrib[todo[i]] = (contrib[todo[i]] * suff[i+1]) % MOD;
}
pref.clear();
suff.clear();
for (auto next: tree[node]) {
calc_c(next);
}
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N;
m = M;
tree.resize(n+m);
w.assign(n+m, 0);
contrib.assign(n+m, 0);
for (int i = 1; i < n + m; i++) {
tree[P[i]].push_back(i);
}
calc_w(0);
calc_c(0);
for (int i = n; i < n + m; i++) {
//cout << "DBG: " << contrib[i] << "\n";
}
ans = 0;
state = A;
for (int i = n; i < n + m; i++) {
if (state[i - n]) {
ans = (ans + contrib[i]) % MOD;
}
}
}
int count_ways(int L, int R) {
for (int i = L; i <= R; i++) {
if (state[i - n]) {
ans = (ans - contrib[i] + MOD) % MOD;
state[i - n] = 0;
}
else {
ans = (ans + contrib[i]) % MOD;
state[i - n] = 1;
}
}
return ans;
}
