#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, inv_f;
std::vector<std::vector<int>> g;
std::vector<int> lazy;
#define LC (2 * v + 1)
#define RC (2 * v + 2)
#define mid ((l + r) / 2)
void push(int v) {
if (lazy[v] == 1) {
std::swap(f[v], inv_f[v]);
}
if (LC < n + m) {
lazy[LC] ^= lazy[v];
}
if (RC < n + m) {
lazy[RC] ^= lazy[v];
}
lazy[v] = 0;
}
void calc(int i) {
{
int v = i;
push(v);
push(LC);
push(RC);
}
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);
inv_f.resize(n + m);
g.resize(n);
for (int i = 0; i < n; i++) {
g[i].resize(inp[i].size() + 1);
}
lazy.resize(n + m);
for (int i = 0; i < m; i++) {
a[i] ^= 1;
}
prep();
for (int i = 0; i < n + m; i++) {
std::swap(f[i], inv_f[i]);
}
for (int i = 0; i < m; i++) {
a[i] ^= 1;
}
prep();
}
void invert(int s, int e, int v = 0, int l = n, int r = n + m) {
push(v);
if (s <= l && r <= e) {
lazy[v] ^= 1;
return;
}
if (s < mid) {
invert(s, e, LC, l, mid);
}
if (e > mid) {
invert(s, e, RC, mid, r);
}
calc(v);
}
int count_ways(int L, int R) {
invert(L, R + 1);
return f[0][1];
}
