#include <bits/stdc++.h>
#include "circuit.h"
#define ll long long
#define fi first
#define se second
using namespace std;
const int maxn = 2e5 + 10, off = (1 << 17), mod = 1e9 + 2022;
int n, m;
int tour[2 * off][2];
int prop[2 * off];
int d[maxn];
int pot[maxn];
vector <int> v[maxn];
//int stanje[maxn];
int fakt[maxn];
int siz[maxn];
int add(int x, int y){
return (x + y) % mod;
}
int mul(int x, int y){
return ((ll)x * y) % mod;
}
void push(int x){
if(x >= off || !prop[x]) return;
prop[x] = 0;
swap(tour[x * 2][0], tour[x * 2][1]);
swap(tour[x * 2 + 1][0], tour[x * 2 + 1][1]);
prop[x * 2] ^= 1;
prop[x * 2 + 1] ^= 1;
}
void update(int x, int lo, int hi, int l, int r){
push(x);
if(hi <= l || r <= lo) return;
if(l <= lo && hi <= r){
swap(tour[x][0], tour[x][1]);
prop[x] = 1;
return;
}
int mid = (lo + hi) / 2;
update(x * 2, lo, mid, l, r);
update(x * 2 + 1, mid, hi, l, r);
tour[x][0] = add(tour[x * 2][0], tour[x * 2 + 1][0]);
tour[x][1] = add(tour[x * 2][1], tour[x * 2 + 1][1]);
}
void dfs1(int x){
// cout << x << endl;
for(int i = 0; i < v[x].size(); i++){
int x2 = v[x][i];
// d[x2] = d[x] + 1;
dfs1(x2);
siz[x] += siz[x2];
}
siz[x] += (x < n);
}
void dfs2(int x){
// cout << x << endl;
if(x >= n) return;
int l = v[x][0];
int r = v[x][1];
fakt[l] = mul(fakt[x], pot[siz[r]]);
fakt[r] = mul(fakt[x], pot[siz[l]]);
dfs2(l);
dfs2(r);
}
void init(int N, int M, vector<int> P, vector<int> A){
n = N;
m = M;
pot[0] = 1;
for(int i = 1; i < maxn; i++){
pot[i] = mul(pot[i - 1], 2);
}
for(int i = 1; i < n + m; i++){
// par[i] = P[i];
v[P[i]].push_back(i);
}
// cout << "tu sam " << endl;
fakt[0] = 1;
dfs1(0);
dfs2(0);
// cout << "ovdje " << endl;
for(int i = 0; i < m; i++){
tour[off + i][A[i]] = fakt[n + i];
// stanje[n + i] = A[i];
}
// for(int i = 0; i < n + m; i++){
// cout << siz[i] << ' ';
// }
// cout << endl;
for(int x = off - 1; x >= 1; x--){
tour[x][0] = add(tour[x * 2][0], tour[x * 2 + 1][0]);
tour[x][1] = add(tour[x * 2][1], tour[x * 2 + 1][1]);
}
// cout << "gotov " << endl;
}
int count_ways(int L, int R){
update(1, 0, off, L - n, R - n + 1);
//
// for(int i = L; i <= R; i++){
// stanje[i] ^= 1;
// }
//
// int sum = 0;
//
// for(int i = n; i < n + m; i++){
// if(stanje[i]) sum = add(sum, pot[d[i] - 1]);
// }
//
// return sum;
return tour[1][1];
}
