#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 200005;
const int MOD = 1e9 + 2022;
int binpow(int n, int k){
int res = 1;
while (k > 0){
if (k & 1) res = 1LL * res * n % MOD;
n = 1LL * n * n % MOD;
k >>= 1;
}
return res;
}
int N, M;
vector<int> A;
int contribution[MaxN];
struct node{
int sum;
int sum2;
bool flag;
node(){
sum = sum2 = 0;
flag = false;
};
};
node tree[4 * MaxN];
void flip(int v){
swap(tree[v].sum, tree[v].sum2);
tree[v].flag ^= 1;
}
void push(int v, int tl, int tr){
if (tl == tr || !tree[v].flag) return;
flip(v << 1);
flip(v << 1 | 1);
tree[v].flag = false;
}
void build(int v, int tl, int tr){
if (tl == tr){
tree[v].sum = A[tl - N] * contribution[tl];
tree[v].sum2 = (!A[tl - N]) * contribution[tl];
return;
}
int tm = (tl + tr) >> 1;
build(v << 1, tl, tm);
build(v << 1 | 1, tm + 1, tr);
tree[v].sum = (tree[v << 1].sum + tree[v << 1 | 1].sum) % MOD;
tree[v].sum2 = (tree[v << 1].sum2 + tree[v << 1 | 1].sum2) % MOD;
}
void update(int v, int tl, int tr, int l, int r){
push(v, tl, tr);
if (l <= tl && tr <= r){
flip(v);
return;
}
if (tl > r || tr < l) return;
int tm = (tl + tr) >> 1;
update(v << 1, tl, tm, l, r);
update(v << 1 | 1, tm + 1, tr, l, r);
tree[v].sum = (tree[v << 1].sum + tree[v << 1 | 1].sum) % MOD;
tree[v].sum2 = (tree[v << 1].sum2 + tree[v << 1 | 1].sum2) % MOD;
}
void update(int l, int r){
update(1, N, N + M - 1, l, r);
}
int get(){
return tree[1].sum;
}
vector<int> g[MaxN];
long long sub[MaxN];
void dfs0(int v){
sub[v] = 1;
if (!g[v].empty()){
sub[v] = sub[v] * (int) g[v].size() % MOD;
}
for (int u : g[v]){
dfs0(u);
sub[v] = sub[v] * sub[u] % MOD;
}
}
void dfs1(int v, long long up){
int sz = (int) g[v].size();
if (sz == 0){
contribution[v] = up % MOD;
return;
}
vector<long long> suff(sz, 1);
for (int i = sz - 1; i >= 0; i--){
int u = g[v][i];
suff[i] = sub[u];
if (i + 1 < sz) {
suff[i] = suff[i] * suff[i + 1] % MOD;
}
}
long long pref = 1;
for (int i = 0; i < sz; i++){
int u = g[v][i];
long long ways = up * pref % MOD;
if (i + 1 < sz) ways = ways * suff[i + 1] % MOD;
dfs1(u, ways);
pref = pref * sub[u] % MOD;
}
}
void init(int _N, int _M, vector<int> P, vector<int> _A) {
N = _N, M = _M, A = _A;
for (int i = 1; i < N + M; i++){
g[P[i]].push_back(i);
}
dfs0(0);
dfs1(0, 1);
build(1, N, N + M - 1);
}
int count_ways(int L, int R) {
update(L, R);
return get();
}
