#include <iostream>
#include <vector>
using i64 = int64_t;
const i64 MOD = 1'000'002'022;
struct Node {
i64 a1, a0;
Node() : a1(0), a0(0) {}
Node(i64 a1, i64 a0) : a1(a1), a0(a0) {}
void toggle() { std::swap(a1, a0); }
Node operator*(const Node &rhs) const {
return {(a1 + rhs.a1) % MOD, (a0 + rhs.a0) % MOD};
}
// Node operator*(const Node &rhs) const {
// return {(a1 * rhs.ax + ax * rhs.a1) % MOD,
// (a0 * rhs.ax + ax * rhs.a0) % MOD, ax * rhs.ax * 2 % MOD};
// }
};
struct SegmentTree {
std::vector<Node> values;
std::vector<bool> toggled;
i64 offset;
SegmentTree() : values{}, toggled{}, offset{0} {}
explicit SegmentTree(size_t sz, const std::vector<i64> contribution)
: values(2 * sz), toggled(2 * sz, false), offset(sz) {
for (i64 i = 0; i < sz; i++) {
i64 c = i < contribution.size() ? contribution[i] : 0;
values[sz + i] = Node(0, c);
}
for (i64 i = sz - 1; i > 0; i--) pull(i);
}
void toggle(i64 idx) {
idx += offset;
values[idx].toggle();
while (idx /= 2) pull(idx);
}
void toggle_range(i64 l, i64 r) { toggle_range(l, r, 1, 0, offset); }
void toggle_range(i64 l, i64 r, i64 v, i64 s, i64 e) {
if (e <= l || r <= s) {
return;
} else if (l <= s && e <= r) {
values[v].toggle();
toggled[v] = !toggled[v];
} else {
i64 m = (s + e) / 2;
push(v);
toggle_range(l, r, 2 * v, s, m);
toggle_range(l, r, 2 * v + 1, m, e);
pull(v);
}
}
void push(i64 v) {
if (toggled[v]) {
toggled[v] = false;
toggled[2 * v] = !toggled[2 * v];
toggled[2 * v + 1] = !toggled[2 * v + 1];
values[2 * v].toggle();
values[2 * v + 1].toggle();
}
}
void pull(i64 v) { values[v] = values[2 * v] * values[2 * v + 1]; }
const Node &root() const { return values[1]; }
};
int n, m;
std::vector<int> p, a;
std::vector<std::vector<int>> children;
std::vector<i64> possible;
std::vector<i64> contribution;
SegmentTree st;
i64 &dfs(int node) {
if (node >= n) return possible[node] = 1;
i64 total = children[node].size();
for (i64 c : children[node]) {
total *= dfs(c);
total %= MOD;
}
return possible[node] = total;
}
void dfs1(int node, int contrib) {
if (node >= n) {
contribution[node - n] = contrib;
return;
}
// std::cerr << node << ' ' << children.size() << ' ' << n << '\n';
i64 cs = children[node].size();
std::vector<i64> xs_left{1}, xs_right{1};
xs_left.reserve(1 + cs);
xs_right.reserve(1 + cs);
for (i64 i = 0; i < cs; i++) {
xs_left.push_back(xs_left.back() * possible[children[node][i]] % MOD);
xs_right.push_back(xs_right.back() *
possible[children[node][cs - i - 1]] % MOD);
}
for (i64 i = 0; i < cs; i++) {
dfs1(children[node][i],
contrib * xs_left[i] % MOD * xs_right[cs - i - 1] % MOD);
}
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N;
m = M;
p = P;
a = A;
children.resize(N);
for (i64 i = 1; i < N + M; i++) {
children[P[i]].push_back(i);
}
possible.resize(N + M);
dfs(0);
contribution.resize(M);
dfs1(0, 1);
i64 o = 1;
while (o < M) o *= 2;
st = SegmentTree(o, contribution);
for (i64 i = 0; i < M; i++) {
if (A[i]) st.toggle(i);
}
}
int count_ways(int l, int r) {
r += 1;
l -= n;
r -= n;
st.toggle_range(l, r);
return st.root().a1;
}
