#include "circuit.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define ff first
#define ss second
const int mod = 1'000'002'022;
void upd(ll &a, ll b) {
a = (a + b) % mod;
if (a < 0) a += mod;
}
int n, m;
vector<int> a, p, height;
vector<vector<int>> g;
vector<array<ll, 2>> dp;
void calc(int u) {
vector<ll> now(g[u].size() + 1);
now[0] = 1;
for (int v: g[u]) {
vector<ll> nw(g[u].size() + 1);
for (int i = g[u].size() - 1; i >= 0; i--) {
upd(nw[i + 1], now[i] * dp[v][1]);
upd(nw[i], now[i] * dp[v][0]);
}
swap(nw, now);
}
dp[u][0] = dp[u][1] = 0;
ll sum0 = accumulate(now.begin(), now.end(), 0ll) % mod, sum1 = 0;
for (int i = g[u].size(); i > 0; i--) {
upd(sum1, now[i]); upd(sum0, -now[i]);
upd(dp[u][1], sum1);
upd(dp[u][0], sum0);
}
}
void dfs(int u) {
if (u >= n) {
dp[u][a[u - n]] = 1; dp[u][!a[u - n]] = 0;
return;
}
for (int v: g[u]) {
height[v] = height[u] + 1;
dfs(v);
}
calc(u);
}
void init(int _n, int _m, std::vector<int> P, std::vector<int> A) {
n = _n, m = _m;
a = A; p = P;
g.assign(n, {});
height.assign(n + m, 0);
dp.assign(n + m, array<ll, 2>{});
for (int i = 1; i < n + m; i++) g[p[i]].emplace_back(i);
dfs(0);
}
int count_ways(int L, int R) {
priority_queue<pair<int, int>> pq;
set<int> vis;
for (int i = L; i <= R; i++) {
a[i - n] = !a[i - n];
dp[i][a[i - n]] = 1; dp[i][!a[i - n]] = 0;
pq.emplace(height[p[i]], p[i]);
}
while (!pq.empty()) {
auto [_, u] = pq.top(); pq.pop();
if (vis.count(u)) continue;
vis.insert(u);
calc(u);
if (u > 0) pq.emplace(height[p[u]], p[u]);
}
return dp[0][1];
}
