#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int SZ = 131072;
const ll MOD = ll(1e9) + 2022;
struct Seg {
int l[2 * SZ];
ll d[2 * SZ], w[2 * SZ];
void i(int n, vector<int> a, vector<ll> v) {
for(int i = 0; i < n; i++) w[i + SZ] = v[i];
for(int i = 0; i < n; i++) if(a[i]) d[i + SZ] = v[i];
for(int i = SZ - 1; i; i--) {
d[i] = (d[2 * i] + d[2 * i + 1]) % MOD;
w[i] = (w[2 * i] + w[2 * i + 1]) % MOD;
}
}
void flp(int x) {
d[x] = (w[x] + MOD - d[x]) % MOD;
l[x] ^= 1;
}
void u(int s, int e, int x = 1, int p = 0, int q = SZ - 1) {
if(e < p || q < s) return;
if(s <= p && q <= e) {
flp(x);
return;
}
if(l[x]) { flp(2 * x); flp(2 * x + 1); l[x] = 0; }
u(s, e, 2 * x, p, (p + q) / 2);
u(s, e, 2 * x + 1, (p + q) / 2 + 1, q);
d[x] = (d[2 * x] + d[2 * x + 1]) % MOD;
}
} S;
int n;
void init(int N, int M, vector<int> P, vector<int> A) {
n = N;
vector<vector<int>> e(N);
for(int i = 1; i < N + M; i++) e[P[i]].push_back(i);
vector<ll> w(N);
for(int i = N - 1; i; i--) {
w[i] = e[i].size();
for(int j : e[i]) if(j < N) (w[i] *= w[j]) %= MOD;
}
vector<ll> v(M);
const function<void(int, ll)> f = [&](int x, ll t) {
if(x >= N) {
v[x - N] = t;
return;
}
vector<ll> sf = {1};
for(int i = int(e[x].size()) - 1; i; i--)
sf.push_back(sf.back() * (e[x][i] < N ? w[e[x][i]] : 1) % MOD);
ll pf = 1;
for(int i : e[x]) {
f(i, t * pf % MOD * sf.back() % MOD);
if(i < N) (pf *= w[i]) %= MOD;
sf.pop_back();
}
};
f(0, 1);
S.i(M, A, v);
}
int count_ways(int L, int R) {
S.u(L - n, R - n);
return S.d[1];
}
