#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ALL(v) (v).begin(), (v).end()
#define MASK(i) (1LL << (i))
#define GETBIT(mask, i) (((mask) >> (i)) & 1)
// mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rng(1);
ll rngesus(ll l, ll r){return ((ull) rng()) % (r - l + 1) + l;}
ll max(ll a, ll b){return (a > b) ? a : b;}
ll min(ll a, ll b){return (a < b) ? a : b;}
ll LASTBIT(ll mask){return mask & (-mask);}
ll pop_cnt(ll mask){return __builtin_popcountll(mask);}
ll ctz(ll mask){return __builtin_ctzll(mask);}
ll clz(ll mask){return __builtin_clzll(mask);}
ll logOf(ll mask){return 63 - clz(mask);}
template <class T1, class T2>
bool minimize(T1 &a, T2 b){
if (a > b){a = b; return true;}
return false;
}
template <class T1, class T2>
bool maximize(T1 &a, T2 b){
if (a < b){a = b; return true;}
return false;
}
template <class T>
void printArr(T& a, string separator = " ", string finish = "\n", ostream& out = cout){
for(auto i: a) out << i << separator;
out << finish;
}
template <class T>
void remove_dup(vector<T> &a){
sort(ALL(a));
a.resize(unique(ALL(a)) - a.begin());
}
const int N = 2e5 + 69, MOD = 1e9 + 2022;
void add(int &a, int b){
a += b;
if (a >= MOD) a -= MOD;
}
void sub(int &a, int b){
a -= b;
if (a < 0) a += MOD;
}
int n, m;
vector<int> graph[N];
int prod[N], val[N];
void dfs(int u, int p){
if (u >= n) return;
prod[u] = graph[u].size();
for(int v: graph[u]) if (v != p){
dfs(v, u);
prod[u] = 1LL * prod[u] * prod[v] % MOD;
}
}
void go(int u, int p, int odd){
if (u >= n){
val[u] = odd;
return;
}
vector<int> pref(graph[u].size() + 1, 1), suff(graph[u].size() + 1, 1);
for(int i = 0; i<graph[u].size(); ++i){
pref[i+1] = 1LL * pref[i] * prod[graph[u][i]] % MOD;
}
for(int i = graph[u].size() - 1; i>=0; --i){
suff[i] = 1LL * suff[i+1] * prod[graph[u][i]] % MOD;
}
for(int i = 0; i<graph[u].size(); ++i){
int cur = 1LL * pref[i] * suff[i+1] % MOD;
go(graph[u][i], u, 1LL * odd * cur % MOD);
}
}
struct SegmentTree{
struct Node{
int sum, cur, lazy;
Node(){sum = cur = lazy = 0;}
};
int n;
vector<Node> a;
SegmentTree(int _n, vector<int> b){
n = _n;
if (n == 0) return;
a.resize(n * 4 + 4);
build_tree(0, n-1, 1, b);
}
Node combine(Node x, Node y){
Node ans = x;
add(ans.sum, y.sum);
add(ans.cur, y.cur);
ans.lazy = 0;
return ans;
}
void flip(Node &x){
x.lazy ^= 1;
x.cur = x.sum-x.cur;
if (x.cur < 0) x.cur += MOD;
}
void build_tree(int l, int r, int id, vector<int> &b){
if (l == r){a[id].sum = b[l]; return;}
int mid = (l + r) >> 1;
build_tree(l, mid, id * 2, b);
build_tree(mid + 1, r, id * 2 + 1, b);
a[id] = combine(a[id * 2], a[id * 2 + 1]);
}
void down(int id){
if (a[id].lazy){
flip(a[id * 2]);
flip(a[id * 2 + 1]);
a[id].lazy = 1;
}
}
void update(int u, int v, int l, int r, int id){
if (u <= l && r <= v){
flip(a[id]);
return;
}
int mid = (l + r) >> 1;
if (a[id].lazy) down(id);
if (u <= mid) update(u, v, l, mid, id * 2);
if (v > mid) update(u, v, mid + 1, r, id * 2 + 1);
a[id] = combine(a[id * 2], a[id * 2 + 1]);
}
void update(int u, int v){return update(u, v, 0, n-1, 1);}
int get(){return a[1].cur;}
};
SegmentTree st(0, vector<int>(0));
void init(int _n, int _m, vector<int> P, vector<int> A) {
n = _n, m = _m;
for(int i = 1; i<n+m; ++i){
graph[P[i]].push_back(i);
}
for(int i = 0; i<m; ++i){
prod[i+n] = 1;
}
dfs(0, 0);
go(0, 0, 1);
vector<int> b;
for(int i = n; i<n+m; ++i) b.push_back(val[i]);
st = SegmentTree(m, b);
for(int i =0; i<m; ++i) if (A[i]) {
st.update(i, i);
}
}
int count_ways(int l, int r) {
l -= n; r -= n;
st.update(l, r);
return st.get();
}
// int main(void){
// ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// int n, m; cin >> n >> m;
// vector<int> P(n+m, -1);
// for(int i = 1; i<n+m; ++i) cin >> P[i];
// vector<int> A(m);
// for(int i = 0; i<m; ++i) cin >> A[i];
// init(n, m, P, A);
// int q; cin >> q;
// while(q--){
// int l, r; cin >> l >> r;
// cout << count_ways(l, r) << "\n";
// }
// return 0;
// }
