#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using i32 = int32_t;
#define int long long
const int MAXN = 2e5 + 5;
const int mod = 1000002022;
int n, m, dp[MAXN], a[MAXN], all[MAXN], mul[MAXN];
vector<int> adj[MAXN];
void Dfs(int u) {
if (u >= n) all[u] = 1;
else all[u] = adj[u].size();
for (auto& v : adj[u]) {
Dfs(v);
(all[u] *= all[v]) %= mod;
}
}
inline int add(int x, int y) {
x += y;
if (x >= mod) x -= mod;
return x;
}
struct SegTree {
int size = 1;
vector<int> seg, off, lazy;
void init(int sz) {
while (size < sz) size *= 2;
seg.assign(2 * size + 10, 0);
off.assign(2 * size + 10, 0);
lazy.assign(2 * size + 10, 0);
}
void push(int id) {
if (lazy[id]) {
swap(seg[id], off[id]);
if (id < size) {
for (int i = 0; i < 2; i++) {
lazy[id * 2 + i] ^= 1;
}
}
}
lazy[id] = 0;
}
void pull(int id) {
seg[id] = add(seg[id * 2], seg[id * 2 + 1]);
off[id] = add(off[id * 2], off[id * 2 + 1]);
}
void build(int l, int r, int id) {
if (l == r) {
if (a[l + n]) {
seg[id] = mul[l + n];
off[id] = 0;
} else {
seg[id] = 0;
off[id] = mul[l + n];
}
return;
}
int mid = (l + r) / 2;
build(l, mid, id * 2);
build(mid + 1, r, id * 2 + 1);
pull(id);
}
void update(int ql, int qr, int l, int r, int id) {
push(id);
if (ql <= l && r <= qr) {
lazy[id] = 1;
push(id);
return;
}
if (qr < l || r < ql) return;
int mid = (l + r) / 2;
update(ql, qr, l, mid, id * 2);
update(ql, qr, mid + 1, r, id * 2 + 1);
pull(id);
}
int query() {
push(1);
return seg[1];
}
} sgt;
void dfs(int u) {
if (u >= n) return;
int sz = adj[u].size();
vector<int> pref(sz, 0), suff(sz, 0);
for (int i = 0; i < sz; i++) {
pref[i] = all[adj[u][i]];
if (i) (pref[i] *= pref[i - 1]) %= mod;
}
for (int i = sz - 1; i >= 0; i--) {
suff[i] = all[adj[u][i]];
if (i + 1 < sz) (suff[i] *= suff[i + 1]) %= mod;
}
for (int i = 0; i < sz; i++) {
int res = 1;
if (i) res = pref[i - 1];
if (i + 1 < sz) (res *= suff[i + 1]) %= mod;
(res *= mul[u]) %= mod;
mul[adj[u][i]] = res;
dfs(adj[u][i]);
}
}
void init(i32 N, i32 M, std::vector<i32> P, std::vector<i32> A) {
n = N;
m = M;
for (int i = 0; i < m; i++) a[i + n] = A[i];
for (int i = 1; i < n + m; i++) adj[P[i]].push_back(i);
Dfs(0);
mul[0] = 1;
dfs(0);
sgt.init(m + 1);
sgt.build(0, m - 1, 1);
}
i32 count_ways(i32 L, i32 R) {
sgt.update(L - n, R - n, 0, m - 1, 1);
return sgt.query();
}
