#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000002022;
vector<vector<int>> v;
vector<vector<ll>> d;
vector<int> A, pr;
int N, M;
void dfs(int x) {
// cout << "ker: " << x << " " << v[x].size() << "\n";
d[x][0] = d[x][1] = 0;
if (x >= N) {
d[x][A[x - N]] = 1;
d[x][A[x - N] ^ 1] = 0;
// cout << x << ": " << d[x][0] << " " << d[x][1] << "\n";
return;
}
for (auto to : v[x])
dfs(to);
vector<int> last(v[x].size() + 1, 0), dp(v[x].size() + 1, 0);
last[0] = 1;
for (auto to : v[x]) {
for (int j = 0; j < v[x].size() + 1; j++) {
if (j) {
dp[j] = last[j - 1] * d[to][1] % MOD;
}
dp[j] += last[j] * d[to][0] % MOD;
dp[j] %= MOD;
}
last = dp;
fill(dp.begin(), dp.end(), 0);
}
int suff = 0, pref = 0;
for (int i = 0; i <= v[x].size(); i++) {
pref += last[i];
pref %= MOD;
// cout << last[i] << " ";
}
// cout << "\n";
for (int i = v[x].size(); i >= 1; i--) {
pref -= last[i];
pref %= MOD;
if (pref < 0) {
pref += MOD;
}
suff += last[i];
suff %= MOD;
d[x][1] += suff;
d[x][1] %= MOD;
d[x][0] += pref;
d[x][0] %= MOD;
}
// dfs(pr[x]);
// cout << x << ": " << d[x][0] << " " << d[x][1] << "\n";
}
void upd(int x) {
d[x][0] = d[x][1] = 0;
if (x >= N) {
d[x][A[x - N]] = 1;
d[x][A[x - N] ^ 1] = 0;
// cout << x << ": " << d[x][0] << " " << d[x][1] << "\n";
upd(pr[x]);
return;
}
vector<int> last(v[x].size() + 1, 0), dp(v[x].size() + 1, 0);
last[0] = 1;
for (auto to : v[x]) {
for (int j = 0; j < v[x].size() + 1; j++) {
if (j) {
dp[j] = last[j - 1] * d[to][1] % MOD;
}
dp[j] += last[j] * d[to][0] % MOD;
dp[j] %= MOD;
}
last = dp;
fill(dp.begin(), dp.end(), 0);
}
int suff = 0, pref = 0;
for (int i = 0; i <= v[x].size(); i++) {
pref += last[i];
pref %= MOD;
// cout << last[i] << " ";
}
// cout << "\n";
for (int i = v[x].size(); i >= 1; i--) {
pref -= last[i];
pref %= MOD;
if (pref < 0) {
pref += MOD;
}
suff += last[i];
suff %= MOD;
d[x][1] += suff;
d[x][1] %= MOD;
d[x][0] += pref;
d[x][0] %= MOD;
}
// cout << x << " " << d[x][0] << " " << d[x][1] << "\n";
if (x)
upd(pr[x]);
}
void init(int N, int M, vector<int> P, vector<int> A) {
pr.resize(N + M);
v.resize(N + M);
d.resize(N + M);
::A = A;
::N = N;
::M = M;
for (int i = 1; i < N + M; i++) {
v[P[i]].push_back(i);
pr[i] = P[i];
// cout << "add " << i << " " << v[i].size() << "\n";
}
for (int i = 0; i < N + M; i++) {
d[i].resize(2);
}
dfs(0);
}
int count_ways(int L, int R) {
for (int i = L; i <= R; i++) {
A[i - N] ^= 1;
}
if (N <= 1000 && M <= 1000) {
dfs(0);
return d[0][1];
}
for (int i = L; i <= R; i++) {
upd(i);
}
return d[0][1];
}
