#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using arl2 = array<ll, 2>;
using arl3 = array<ll, 3>;
template <class T> using vt = vector<T>;
#define all(x) begin(x), end(x)
#define size(x) (int((x).size()))
#define REP(a,b,c,d) for(int a=(b);(d)>0?a<=(c):a>=(c);a+=(d))
#define FOR(a,b,c) REP(a,b,c,1)
#define ROF(a,b,c) REP(a,b,c,-1)
constexpr int mxN = 200005, MOD = 1000002022;
int N, M, tl[mxN], tr[mxN], lz[mxN];
vt<int> P, A;
vt<int> adj[mxN];
int dp0[mxN], dp1[mxN];
vt<vt<ari2>> dp[mxN];
void apply(const int i) {
lz[i] ^= 1;
swap(dp0[i], dp1[i]);
if (i >= N)
return;
FOR(j, 1, size(adj[i]))
FOR(k, 1, j)
swap(dp[i][j][k][0], dp[i][j][k][1]);
}
void push(const int i) {
if (!lz[i])
return;
for (const auto &j : adj[i])
apply(j);
lz[i] = 0;
}
void pull(const int i) {
FOR(j, 0, size(adj[i]) - 1) {
FOR(k, 0, j+1) {
dp[i][j+1][k][1] = (k ? 1ll * dp[i][j][k-1][1] * dp1[adj[i][j]] % MOD : 0) + dp[i][j][k][1] * dp0[adj[i][j]] % MOD;
dp[i][j+1][k][1] %= MOD;
dp[i][j+1][k][0] = (k ? 1ll * dp[i][j][k-1][0] * dp0[adj[i][j]] % MOD : 0) + dp[i][j][k][0] * dp1[adj[i][j]] % MOD;
dp[i][j+1][k][0] %= MOD;
}
}
dp0[i] = dp1[i] = 0;
FOR(x, 1, size(adj[i])) {
dp0[i] += 1ll * dp[i][size(adj[i])][x][0] * x % MOD;
dp0[i] %= MOD;
dp1[i] += 1ll * dp[i][size(adj[i])][x][1] * x % MOD;
dp1[i] %= MOD;
}
}
void update(const int ql, const int qr, const int i) {
if (tl[i] > qr || tr[i] < ql)
return;
if (ql <= tl[i] && tr[i] <= qr)
apply(i);
else {
push(i);
for (const auto &j : adj[i])
update(ql, qr, j);
pull(i);
}
}
int count_ways(int L, int R) {
update(L, R, 0);
return dp1[0];
}
void init_dfs(const int i) {
if (N <= i) {
dp0[i] = !A[i-N];
dp1[i] = A[i-N];
tl[i] = tr[i] = i;
return;
}
tl[i] = INT_MAX;
tr[i] = -1;
dp[i].assign(size(adj[i]) + 1, vt<ari2>(size(adj[i]) + 1));
dp[i][0][0] = {1, 1};
for (const auto &j : adj[i]) {
init_dfs(j);
tr[i] = max(tr[i], tr[j]);
tl[i] = min(tl[i], tl[j]);
}
pull(i);
}
void init(int _N, int _M, vt<int> _P, vt<int> _A) {
N = _N, M = _M, P = _P, A = _A;
FOR(i, 1, N+M-1)
adj[P[i]].push_back(i);
init_dfs(0);
}
