#include "circuit.h"
// #include <vector>
#include <bits/stdc++.h>
using i64 = long long;
constexpr int mod = 1'000'002'022;
int n, m;
std::vector<int> p, a;
std::vector<std::vector<int>> inp;
std::vector<std::array<int, 2>> f;
std::vector<std::vector<int>> g;
void calc(int i) {
f[i] = {0, 0};
std::fill(g[i].begin(), g[i].end(), 0);
g[i][0] = 1;
for (int j : inp[i]) {
std::vector<int> new_g(g[i].size());
new_g[0] = i64(g[i][0]) * f[j][0] % mod;
for (int k = 1; k < g[i].size(); k++) {
new_g[k] = (i64(g[i][k]) * f[j][0] % mod
+ i64(g[i][k - 1]) * f[j][1] % mod) % mod;
}
g[i] = new_g;
}
int less = g[i][0];
int more = std::accumulate(g[i].begin() + 1, g[i].end(), 0ll) % mod;
for (int t = 1; t < g[i].size(); t++) {
f[i][0] = (f[i][0] + less) % mod;
f[i][1] = (f[i][1] + more) % mod;
less = (less + g[i][t]) % mod;
more = (more - g[i][t] + mod) % mod;
}
}
void prep() {
for (int i = n; i < n + m; i++) {
f[i][a[i - n]] = 1;
}
for (int i = n - 1; i >= 0; i--) {
calc(i);
}
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N;
m = M;
p = P;
a = A;
inp.resize(n);
for (int i = 1; i < n + m; i++) {
inp[p[i]].push_back(i);
}
for (int i = 0; i < n; i++) {
assert(inp[i].size() < n + m);
}
f.resize(n + m);
g.resize(n);
for (int i = 0; i < n; i++) {
g[i].resize(inp[i].size() + 1);
}
prep();
}
int count_ways(int L, int R) {
assert(L == R);
int i = L = R;
a[i - n] ^= 1;
f[i] = {0, 0};
f[i][a[i - n]] = 1;
while (0 < i) {
calc(i >>= 1);
}
return f[0][1];
}
