#include "circuit.h"
#include <bits/stdc++.h>
#define maxn 1005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
constexpr int mod = 1'000'002'022;
inline constexpr void add(int &x, const int &y) {x += y; if (x >= mod) x -= mod;}
int a[maxn], n, m;
vector<int> adj[maxn];
int dp[maxn+maxn][2], f[maxn], c[maxn];
ii lis[maxn];
void pfs(int u) {
if (u >= n) {
c[u] = 0;
return;
}
c[u] = 1;
for (int v : adj[u]) {
pfs(v);
if (v < n) c[u] = 1LL * c[u] * c[v] % mod;
}
c[u] = 1LL * c[u] * int(adj[u].size()) % mod;
}
void init(int N, int M, vector<int> P, vector<int> A) {
for (int i = 1; i < N+M; i++) adj[P[i]].emplace_back(i);
for (int i = 0; i < M; i++) a[i+1] = A[i];
n = N;
m = M;
pfs(0);
}
void dfs(int u) {
if (u >= n) {
dp[u][a[u-n+1]] = 1;
dp[u][1^a[u-n+1]] = 0;
return;
}
int sz = 0;
for (int v : adj[u]) {
dfs(v);
lis[++sz] = ii{dp[v][0], dp[v][1]};
}
for (int i = 0; i <= sz; i++) f[i] = 0;
f[0] = 1;
for (int i = 1; i <= sz; i++) {
for (int j = sz; j >= 1; j--)
f[j] = (1LL * f[j] * lis[i].fi + 1LL * f[j-1] * lis[i].se) % mod;
f[0] = 1LL * f[0] * lis[i].fi % mod;
}
int sum = 0;
dp[u][0] = dp[u][1] = 0;
for (int i = sz; i >= 1; i--) {
add(sum, f[i]);
add(dp[u][1], sum);
}
dp[u][0] = (c[u]-dp[u][1]+mod)%mod;
}
int count_ways(int L, int R) {
for (int i = L-n+1; i <= R-n+1; i++) a[i] ^= 1;
dfs(0);
return dp[0][1];
}
/*
3 4 3
-1 0 1 2 1 1 0
1 0 1 0
3 4
4 5
3 6
2 0 6
*/
