#include <bits/stdc++.h>
using namespace std;
namespace {
int N, M;
vector<vector<int>> adj;
using int64 = long long;
const int md = 1000002022;
class lazy_segment_tree {
struct node {
int64 zs, os;
node operator+(const node &r) const { return {(zs + r.zs) % md, (os + r.os) % md}; }
};
int n;
vector<node> seg;
vector<int> lazy;
void build(int v, int tl, int tr, const vector<int64> &a) {
if (tl == tr) {
seg[v] = {a[tl], 0};
return;
}
int tm = (tl + tr) / 2;
build(2 * v, tl, tm, a), build(2 * v + 1, tm + 1, tr, a);
seg[v] = seg[2 * v] + seg[2 * v + 1];
}
void push(int v) {
if (lazy[v]) {
swap(seg[v].zs, seg[v].os);
}
if (v < 2 * n) {
lazy[2 * v] ^= lazy[v];
lazy[2 * v + 1] ^= lazy[v];
}
lazy[v] = 0;
}
void pull(int v) {
seg[v] = seg[2 * v] + seg[2 * v + 1];
}
void toggle(int v, int tl, int tr, int l, int r) {
push(v);
if (r < tl || tr < l) {
return;
}
if (l <= tl && tr <= r) {
lazy[v] ^= 1;
push(v);
return;
}
int tm = (tl + tr) / 2;
toggle(2 * v, tl, tm, l, r), toggle(2 * v + 1, tm + 1, tr, l, r);
pull(v);
}
public:
lazy_segment_tree() {}
lazy_segment_tree(int n, const vector<int64> &a) : n(n), seg(4 * n), lazy(8 * n) {
build(1, 0, n - 1, a);
}
void toggle(int l, int r) {
toggle(1, 0, n - 1, l, r);
}
int64 query() { return seg[1].os; }
};
int64 binexp(int64 a, int b) {
int64 ans = 1, v = a;
while (b) {
if (b & 1) {
ans = (ans * v) % md;
}
b >>= 1;
v = (v * v) % md;
}
return ans;
}
lazy_segment_tree st;
} // namespace
void init(int N, int M, vector<int> P, vector<int> A) {
::N = N, ::M = M;
adj = vector<vector<int>>(N + M);
for (int i = 1; i < N + M; ++i) {
adj[P[i]].push_back(i);
}
vector<int64> sz(N + M);
auto dfs = [&](auto &&self, int u) -> void {
sz[u] = !adj[u].empty();
for (int &i : adj[u]) {
self(self, i);
sz[u] += sz[i];
}
if (!adj[u].empty()) {
assert(adj[u].size() == 2);
swap(sz[adj[u][0]], sz[adj[u][1]]);
}
};
dfs(dfs, 0);
sz[0] = 0;
vector<int64> a(M);
auto dfs2 = [&](auto &&self, int u, int64 prod) -> void {
prod *= binexp(2, sz[u]);
if (u >= N) {
a[u - N] = prod;
}
for (int &i : adj[u]) {
self(self, i, prod);
}
};
dfs2(dfs2, 0, 1);
st = lazy_segment_tree(M, a);
for (int i = 0; i < M; ++i) {
if (A[i]) {
st.toggle(i, i);
}
}
}
int count_ways(int L, int R) {
st.toggle(L - N, R - N);
return st.query();
}
#ifdef MACOS_LOCAL
#include "stub.cpp"
#endif
