#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 1000002022;
const int MN = 1e5+5;
const int BLOCK = 350;
int n, m;
vector<vector<int>> tree;
vector<ll> contrib, w, blockOn, blockOff;
vector<int> state, block, blockL, blockR;
vector<bool> blockRev;
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]] = contrib[node];
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 upd(int idx) {
if (blockR[idx] == 0) return;
int l = blockL[idx], r = blockR[idx];
blockOn[idx] = 0;
blockOff[idx] = 0;
for (int i = l; i <= r; i++) {
if (blockRev[idx]) state[i - n] = !state[i - n];
if (state[i - n]) {
blockOn[idx] = (blockOn[idx] + contrib[i]) % MOD;
}
else {
blockOff[idx] = (blockOff[idx] + contrib[i]) % MOD;
}
}
blockRev[idx] = false;
}
void init_sqrt() {
blockL.assign(BLOCK+1, 0);
blockR.assign(BLOCK+1, 0);
block.assign(n+m, 0);
blockRev.assign(BLOCK+1, false);
blockOn.assign(BLOCK+1, 0);
blockOff.assign(BLOCK+1, 0);
int curr = 0;
for (int i = n; i < n+m; i += BLOCK) {
blockL[curr] = i;
for (int j = i; j < min(n+m, i + BLOCK); j++) {
block[j] = curr;
blockR[curr] = j;
}
curr++;
}
for (int i = 0; i < BLOCK; i++) {
upd(i);
}
}
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);
contrib[0] = 1;
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;
}
}
init_sqrt();
}
void dbg(ll x) {
//cout << "DEBUG: " << x << "\n";
}
int count_ways(int L, int R) {
int idxL = block[L], idxR = block[R];
if (blockRev[idxL]) {
ans = (ans - blockOff[idxL] + MOD) % MOD;
}
else {
ans = (ans - blockOn[idxL] + MOD) % MOD;
}
while (block[L] == idxL) {
state[L - n] = !state[L - n];
L++;
if (L > R) break;
}
dbg(ans);
upd(idxL);
ans = (ans + blockOn[idxL]) % MOD;
dbg(ans);
if (L > R) return ans;
idxL = block[L];
if (blockRev[idxR]) {
ans = (ans - blockOff[idxR] + MOD) % MOD;
}
else {
ans = (ans - blockOn[idxR] + MOD) % MOD;
}
while (block[R] == idxR) {
state[R - n] = !state[R - n];
R--;
if (L > R) break;
}
upd(idxR);
ans = (ans + blockOn[idxR]) % MOD;
if (L > R) return ans;
idxR = block[R];
for (int i = idxL; i <= idxR; i++) {
if (blockRev[i]) {
ans = (ans - blockOff[i] + MOD) % MOD;
ans = (ans + blockOn[i]) % MOD;
}
else {
ans = (ans - blockOn[i] + MOD) % MOD;
ans = (ans + blockOff[i]) % MOD;
}
blockRev[i] = !blockRev[i];
}
return ans;
}
