#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
typedef long long ll;
const int N = (int)2e5 + 10;
const int MOD = (int)1e9 + 2022;
vector<int> T[N];
int W[N];
int n, m;
void dfs0(int u){
if(T[u].empty()) W[u] = 1;
else{
W[u] = 1;
for(auto x : T[u]){
dfs0(x);
W[u] = (W[u] * 1ll * W[x]) % MOD;
}
W[u] = (W[u] * 1ll * T[u].size()) % MOD;
}
}
int coeff[N];
void dfs1(int u, int wei){
if(T[u].empty()){
coeff[u - n] = wei;
return;
}
vector<int> pre, suff;
for(auto x : T[u]){
pre.push_back(W[x]);
suff.push_back(W[x]);
}
for(int i = 1; i < pre.size(); i ++ ){
pre[i] = (pre[i - 1] * 1ll * pre[i]) % MOD;
}
for(int i = (int)suff.size() - 2; i >= 0 ; i -- ){
suff[i] = (suff[i] * 1ll * suff[i + 1]) % MOD;
}
int cf;
for(int i = 0 ;i < T[u].size(); i ++ ){
cf = 1;
if(i) cf = (cf * 1ll * pre[i - 1]) % MOD;
if(i + 1 < T[u].size()) cf = (cf * 1ll * suff[i + 1]) % MOD;
dfs1(T[u][i], (wei * 1ll * cf) % MOD);
}
}
vector<int> A;
struct Node{
int total;
int cum;
int flip;
};
Node tr[N * 4 + 512];
void build(int node, int cl, int cr){
tr[node].total = 0;
tr[node].cum = 0;
tr[node].flip = 0;
if(cl == cr){
tr[node].total = coeff[cl];
if(A[cl]) tr[node].cum = coeff[cl];
return;
}
int mid = (cl + cr) / 2;
build(node * 2, cl, mid);
build(node * 2 + 1, mid + 1, cr);
tr[node].total = (tr[node * 2].total + tr[node * 2 + 1].total) % MOD;
tr[node].cum = (tr[node * 2].cum + tr[node * 2 + 1].cum) % MOD;
}
void init(int _n, int _m, std::vector<int> P, vector<int> _A) {
n = _n;
m = _m;
A = _A;
for(int i = 1; i < n + m; i ++ ){
T[P[i]].push_back(i);
}
dfs0(0);
dfs1(0, 1);
build(1, 0, m - 1);
}
void push(int node, int cl, int cr){
if(tr[node].flip){
tr[node].cum = (tr[node].total - tr[node].cum + MOD) % MOD;
if(cl != cr){
tr[node * 2].flip ^= 1;
tr[node * 2 + 1].flip ^= 1;
}
tr[node].flip = 0;
}
}
void inv(int node, int cl, int cr, int tl, int rr){
push(node, cl, cr);
if(cr < tl || cl > rr) return;
if(cl >= tl && cr <= rr){
tr[node].flip=1;
push(node,cl,cr);
return;
}
int mid = (cl + cr) / 2;
inv(node * 2, cl, mid, tl, rr);
inv(node * 2 + 1, mid + 1, cr, tl, rr);
tr[node].cum = (tr[node * 2].cum + tr[node * 2 + 1].cum) % MOD;
}
int count_ways(int li, int ri) {
inv(1, 0, m - 1, li - n, ri - n);
return tr[1].cum;
}
