#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll = long long;
const int MOD = (int)1e9 + 2022;
int N, M;
vector<int> A, P, tot_mem, dp_mem;
vector<vector<int> > adj;
int tot(int u) {
if (tot_mem[u] != -1) {
return tot_mem[u];
}
if (u >= N) {
return tot_mem[u] = 1;
}
int ret = (int)(adj[u].size());
for (auto v : adj[u]) {
ret = ((ll)ret * (ll)tot(v)) % MOD;
}
return tot_mem[u] = ret;
}
int dp(int u) {
if (dp_mem[u] != -1) {
return dp_mem[u];
}
if (u >= N) {
return dp_mem[u] = A[u - N];
}
vector<int> sub_dp((int)adj[u].size() + 1, 0);
sub_dp[0] = 1;
for (auto v : adj[u]) {
vector<int> new_sub_dp((int)adj[u].size() + 1);
for (int i = 0; i <= (int)adj[u].size(); i++) {
new_sub_dp[i] = ((i ? (ll)sub_dp[i - 1] * dp(v) : 0ll) % MOD + (ll)sub_dp[i] * ((ll)tot(v) - dp(v)) % MOD) % MOD;
if (new_sub_dp[i] < 0) {
new_sub_dp[i] += MOD;
}
}
sub_dp = new_sub_dp;
}
int ret = 0;
for (int i = 0; i <= (int)adj[u].size(); i++) {
ret = (ret + (ll)i * sub_dp[i] % MOD) % MOD;
}
return dp_mem[u] = ret;
}
void init(int N, int M, vector<int> P, vector<int> A) {
::N = N;
::M = M;
::P = P;
::A = A;
adj.resize(N + M);
tot_mem = dp_mem = vector<int>(N + M, -1);
for (int i = 1; i < N + M; i++) {
adj[P[i]].pb(i);
}
}
int count_ways(int L, int R) {
for (int i = L - N; i <= R - N; i++) {
A[i] = !A[i];
}
for (int i = L; i <= R; i++) {
for (int u = i; u != -1 && dp_mem[u] != -1; u = P[u]) {
dp_mem[u] = -1;
}
}
return dp(0);
}
