#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;
vector<vector<int> > adj;
void init(int N, int M, vector<int> P, vector<int> A) {
::N = N;
::M = M;
::A = A;
adj.resize(N + M);
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];
}
vector<int> tot_mem(N + M, -1), dp_mem(N + M, -1);
function<int(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;
};
function<int(int)> dp = [&](int u) {
if (dp_mem[u] != -1) {
return dp_mem[u];
}
if (u >= N) {
return dp_mem[u] = A[u - N];
}
int ret = 0;
for (int bm = 0; bm < (1 << (int)adj[u].size()); bm++) {
int cur = __builtin_popcount(bm);
for (int i = 0; i < (int)adj[u].size(); i++) {
int tmp = (bm & (1 << i) ? dp(adj[u][i]) : tot(adj[u][i]) - dp(adj[u][i])) % MOD;
if (tmp < 0) {
tmp += MOD;
}
cur = (ll)cur * (ll)tmp % MOD;
}
ret = (ret + cur) % MOD;
}
return dp_mem[u] = ret;
};
return dp(0);
}
