#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const int MaxN = 200005;
const int MOD = 1e9 + 2022;
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];
int dep[MaxN];
void dfs(int v, int p, map<int, int> mp){
int sz = (int) g[v].size();
if (sz == 0){
int &res = contribution[v];
res = 1;
for (auto [d, cnt] : mp){
while (cnt--) res = 1LL * res * d % MOD;
}
} else {
mp[sz]--;
}
for (int u : g[v]){
if (u != p){
dfs(u, v, mp);
}
}
}
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);
}
map<int, int> mp;
for (int i = 0; i < N; i++){
mp[(int) g[i].size()]++;
}
dfs(0, -1, mp);
build(1, N, N + M - 1);
}
int count_ways(int L, int R) {
update(L, R);
return get();
}
