#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MOD = 1e9 + 2022;
#define all(x) x.begin(), x.end()
#define sz(x) (int) x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
int n, m;
vector<int> val, tot, a, lazy;
vector<vector<int>> filhos;
vector<ll> seg, sum;
ll calc_tot(int x) {
if(x >= n) return 1;
tot[x] = sz(filhos[x]);
for(int viz : filhos[x]) {
tot[x] = (tot[x] * calc_tot(viz))%MOD;
}
return tot[x];
}
void dfs(int x) {
ll at = 1;
if(x >= n) return;
for(auto viz : filhos[x]) {
val[viz] = (val[x] * at)%MOD;
if(viz < n) at = (at*tot[viz])%MOD;
}
reverse(all(filhos[x]));
at = 1;
for(auto viz : filhos[x]) {
val[viz] = (val[viz] * at)%MOD;
if(viz < n) at = (at*tot[viz])%MOD;
}
for(auto viz : filhos[x]) dfs(viz);
}
void build(int node, int l, int r) {
if(l == r) {
seg[node] = val[l+n] * a[l];
sum[node] = val[l+n];
return;
}
int mid = (l+r)/2;
build(2*node, l, mid);
build(2*node+1, mid+1, r);
seg[node] = seg[2*node] + seg[2*node+1];
sum[node] = sum[2*node] + sum[2*node+1];
}
void prop(int node, bool folha) {
lazy[node] %= 2;
if(!lazy[node]) return;
seg[node] = sum[node] - seg[node];
lazy[node] = 0;
if(!folha) {
lazy[2*node]++;
lazy[2*node+1]++;
}
}
void update(int node, int l, int r, int p, int q) {
prop(node, l == r);
if(r < p or q < l) return;
if(p <= l and r <= q) {
lazy[node] = 1;
prop(node, l == r);
return;
}
int mid = (l+r)/2;
update(2*node, l, mid, p, q);
update(2*node+1, mid+1, r, p, q);
seg[node] = seg[2*node] + seg[2*node+1];
sum[node] = sum[2*node] + sum[2*node+1];
}
void init(int N, int M, vector<int> P, vector<int> A) {
val.resize(N+M);
tot.resize(N);
filhos.resize(N);
a = A;
n = N;
m = M;
seg.resize(4*M);
sum.resize(4*M);
lazy.resize(4*M);
for(int i = 1; i < N+M; i++)
filhos[P[i]].pb(i);
calc_tot(0);
val[0] = 1;
dfs(0);
build(1, 0, M-1);
}
int count_ways(int L, int R) {
update(1, 0, m-1, L-n, R-n);
return seg[1]%MOD;
}
