#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
struct node {
long long sum1 = 0;
long long sum2 = 0;
bool flip = false;
};
const long long mod = 1e9 + 2022;
const int maxN = 1e5 + 20;
long long cont[maxN * 2];
long long ways[maxN * 2];
node tree[maxN * 4];
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 flip(int id) {
swap(tree[id].sum1, tree[id].sum2);
tree[id].flip ^= 1;
}
void merge(int id) {
tree[id].sum1 = (tree[id * 2].sum1 + tree[id * 2 + 1].sum1) % mod;
tree[id].sum2 = (tree[id * 2].sum2 + tree[id * 2 + 1].sum2) % mod;
tree[id].flip = false;
}
void build(int id, int lt, int rt) {
if (lt == rt) {
tree[id].sum1 = A[lt] ? cont[N + lt] : 0;
tree[id].sum2 = !A[lt] ? cont[N + lt] : 0;
tree[id].flip = false;
return;
}
int mt = (lt + rt) / 2;
build(id * 2, lt, mt);
build(id * 2 + 1, mt + 1, rt);
merge(id);
}
void update(int id, int lt, int rt, int ql, int qr) {
if (lt == ql && rt == qr) {
flip(id);
return;
}
if (tree[id].flip) {
flip(id * 2);
flip(id * 2 + 1);
}
int mt = (lt + rt) / 2;
if (qr <= mt) {
update(id * 2, lt, mt, ql, qr);
}
else if (ql >= mt + 1) {
update(id * 2 + 1, mt + 1, rt, ql, qr);
}
else {
update(id * 2, lt, mt, ql, mt);
update(id * 2 + 1, mt + 1, rt, mt + 1, qr);
}
merge(id);
}
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);
build(1, 1, M);
}
int count_ways(int L, int R) {
L -= N - 1;
R -= N - 1;
update(1, 1, M, L, R);
return tree[1].sum1;
}
