#include <iostream>
#include <vector>
using i64 = int64_t;
const i64 MOD = 1'000'002'022;
struct Node {
i64 a1, a0, ax;
Node() : a1(0), a0(1), ax(1) {}
explicit Node(bool value) : a1(value), a0(!value), ax(1) {}
Node(i64 a1, i64 a0, i64 ax) : a1(a1), a0(a0), ax(ax) {}
void toggle() { std::swap(a1, a0); }
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)
: values(2 * sz), toggled(2 * sz, false), offset(sz) {}
void update(i64 idx, bool value) {
idx += offset;
values[idx] = Node(value);
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;
SegmentTree st;
bool is_45 = true;
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);
}
if (M == N + 1 && (M & (M - 1)) == 0) {
for (i64 i = 0; i < N; i++) {
if (children[i].size() != 2) {
is_45 = false;
break;
}
}
}
if (is_45) {
st = SegmentTree(N + 1);
for (i64 i = 0; i < M; i++) {
st.update(i, A[i]);
}
}
}
auto dfs(int node) -> std::pair<i64, i64> {
if (node >= n) {
return {a[node - n] ? 1 : 0, 1};
}
i64 cs = children[node].size();
std::vector<std::pair<i64, i64>> results;
results.reserve(1 + cs);
for (i64 c : children[node]) {
results.push_back(dfs(c));
}
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() * results[i].second % MOD);
xs_right.push_back(xs_right.back() * results[cs - i - 1].second % MOD);
}
i64 sum = 0, of = cs;
for (i64 i = 0; i < cs; i++) {
sum += results[i].first * xs_left[i] % MOD * xs_right[cs - i - 1];
of *= results[i].second;
sum %= MOD;
of %= MOD;
}
return {sum, of};
}
int count_ways(int l, int r) {
r += 1;
l -= n;
r -= n;
if (is_45) {
st.toggle_range(l, r);
return st.root().a1;
} else {
for (i64 i = l; i < r; i++) {
a[i] = !a[i];
}
return dfs(0).first;
}
}
