#include <bits/stdc++.h>
using namespace std;
namespace {
int N, M;
vector<vector<int>> adj;
vector<int> A;
using int64 = long long;
const int md = 1000002022;
} // namespace
void init(int N, int M, vector<int> P, vector<int> A) {
::N = N, ::M = M;
adj.resize(N + M + 1);
for (int i = 1; i < N + M; ++i) {
adj[P[i]].push_back(i);
}
::A = A;
}
int count_ways(int L, int R) {
for (int i = L; i <= R; ++i) {
A[i - N] = 1 - A[i - N];
}
auto dfs = [&](auto &&self, int u) -> pair<int64, int64> {
if (u >= N) {
return {1 - A[u - N], A[u - N]};
}
vector<int64> poly(adj[u].size() + 1);
poly[0] = 1;
for (int &i : adj[u]) {
auto [f0, g0] = self(self, i);
vector<int64> p = {f0, g0};
vector<int64> mulr(adj[u].size() + 1);
for (int i = 0; i < int(poly.size()); ++i) {
for (int j = 0; j < 2 && i + j < int(mulr.size()); ++j) {
mulr[i + j] = (mulr[i + j] + (poly[i] * p[j]) % md) % md;
}
}
poly = mulr;
}
auto suff = poly, pref = poly;
for (int i = int(poly.size()) - 2; i >= 0; --i) {
suff[i] = (suff[i] + suff[i + 1]) % md;
}
for (int i = 1; i < int(poly.size()); ++i) {
pref[i] = (pref[i - 1] + pref[i]) % md;
}
int64 with = 0, without = 0;
for (int i = 1; i <= int(adj[u].size()); ++i) {
with = (with + suff[i]) % md;
without = (without + pref[i - 1]) % md;
}
return {without, with};
};
return dfs(dfs, 0).second;
}
#ifdef MACOS_LOCAL
#include "stub.cpp"
#endif
