// In the name of Allah
#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define endl '\n'
#define sep ' '
#define F first
#define S second
#define Mp make_pair
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
const int maxn = (1 << 18) + 4;
const int mod = 1e9 + 2022;
struct node {
int lazy; ll ans, ansx;
};
int n, m;
vector<int> adj[maxn]; int D[maxn];
ll valx[maxn], valr[maxn];
ll sm1[maxn], sm2[maxn];
ll val[maxn]; int A[maxn];
node t[maxn];
void pre_dfs(int v) {
if (len(adj[v]) == 0) valx[v] = 1;
else valx[v] = D[v];
for (int u : adj[v]) {
pre_dfs(u);
valx[v] *= valx[u]; valx[v] %= mod;
}
}
void res_dfs(int v) {
for (int j = 0; j <= len(adj[v]); j++) {
if (j == 0) sm1[j] = 1;
else {
int u = adj[v][j - 1];
sm1[j] = sm1[j - 1] * valx[u] % mod;
}
}
for (int j = 0; j <= len(adj[v]); j++) {
if (j == 0) sm2[j] = 1;
else {
int u = adj[v][len(adj[v]) - j];
sm2[j] = sm2[j - 1] * valx[u] % mod;
}
}
val[v] = valr[v] * sm1[len(adj[v])] % mod;
for (int j = 0; j < len(adj[v]); j++) {
int u = adj[v][j];
valr[u] = valr[v] * sm1[j] % mod * sm2[len(adj[v]) - j - 1] % mod;
}
for (int u : adj[v]) {
res_dfs(u);
}
}
node f(node a, node b, int lazy) {
node res; res.lazy = 0;
res.ans = (a.ans + b.ans) % mod;
res.ansx = (a.ansx + b.ansx) % mod;
if (lazy) {
res.lazy ^= 1;
swap(res.ans, res.ansx);
}
return res;
}
void build(int v, int tl, int tr) {
t[v].lazy = 0;
if (tr - tl == 1) {
t[v].ans = val[tl]; t[v].ansx = 0;
if (!A[tl]) swap(t[v].ans, t[v].ansx);
return ;
}
int mid = (tl + tr) / 2;
build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
t[v] = f(t[2 * v + 1], t[2 * v + 2], t[v].lazy);
}
void rev_val(int v, int tl, int tr, int l, int r) {
l = max(l, tl); r = min(r, tr);
if (l >= tr || r <= tl) return ;
if (l == tl && r == tr) {
t[v].lazy ^= 1;
swap(t[v].ans, t[v].ansx);
return ;
}
int mid = (tl + tr) / 2;
rev_val(2 * v + 1, tl, mid, l, r); rev_val(2 * v + 2, mid, tr, l, r);
t[v] = f(t[2 * v + 1], t[2 * v + 2], t[v].lazy);
}
void init(int N, int M, vector<int> Px, vector<int> Ax) {
n = N; m = M;
for (int i = 1; i < n + m; i++) {
adj[Px[i]].pb(i); D[Px[i]]++;
}
pre_dfs(0);
valr[0] = 1; res_dfs(0);
for (int i = 0; i < m; i++) {
val[i] = val[i + n]; A[i] = Ax[i];
}
build(0, 0, m);
}
int count_ways(int L, int R) {
rev_val(0, 0, m, L - n, R - n + 1);
return t[0].ans;
}
