#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 2022;
const int maxN = 1e5 + 20;
long long cont[maxN * 2];
long long ways[maxN * 2];
vector<int> ch[maxN];
int A[maxN];
int N, M;
void dfs1(int u) {
if (ch[u].empty()) {
ways[u] = 1;
return;
}
ways[u] = (int)ch[u].size();
for (auto v: ch[u]) {
dfs1(v);
ways[u] = ways[u] * ways[v] % mod;
}
}
void dfs2(int u) {
if (ch[u].empty()) {
return;
}
int sz = ch[u].size();
vector<long long> pref(sz);
vector<long long> suf(sz);
pref[0] = ways[ch[u][0]];
for (int i = 1; i < sz; i++) {
pref[i] = pref[i - 1] * ways[ch[u][i]] % mod;
}
suf[sz - 1] = ways[ch[u][sz - 1]];
for (int i = sz - 2; i >= 0; i--) {
suf[i] = suf[i + 1] * ways[ch[u][i]] % mod;
}
for (int i = 0; i < sz; i++) {
cont[ch[u][i]] = cont[u] * (i > 0 ? pref[i - 1] : 1) % mod * (i < sz - 1 ? suf[i + 1] : 1) % mod;
dfs2(ch[u][i]);
}
}
void init(int _N, int _M, vector<int> P, vector<int> _A) {
N = _N;
M = _M;
for (int i = 2; i <= N + M; i++) {
ch[P[i - 1] + 1].push_back(i);
}
for (int i = 1; i <= M; i++) {
A[i] = _A[i - 1];
}
dfs1(1);
cont[1] = 1;
dfs2(1);
}
int count_ways(int L, int R) {
L -= N - 1;
R -= N - 1;
for (int i = L; i <= R; i++) {
A[i] ^= 1;
}
long long res = 0;
for (int i = 1; i <= M; i++) {
if (A[i]) {
res += cont[i + N];
res %= mod;
}
}
return res;
}
