#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "circuit.h"
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 6e5 + 10;
const int mod = 1e9 + 2022;
int n, m;
vector <int> g[N];
int sz[N];
void dfs(int u) {
sz[u] = (u >= n ? 1 : g[u].size());
for (auto v: g[u]) {
dfs(v);
sz[u] = 1LL * sz[u] * sz[v] % mod;
}
}
int c[N], prf[N], suf[N];
int mul[N];
void fix(int u) {
int num = 0;
for (auto v: g[u]) c[++num] = v;
prf[0] = suf[num + 1] = 1;
for (int i = 1; i <= num; ++i) prf[i] = 1LL * prf[i - 1] * sz[c[i]] % mod;
for (int i = num; i >= 1; --i) suf[i] = 1LL * suf[i + 1] * sz[c[i]] % mod;
for (int i = 1; i <= num; ++i)
mul[c[i]] = 1LL * prf[i - 1] * suf[i + 1] % mod;
for (auto v: g[u]) fix(v);
}
int ans = 0;
void add(int& a, int b) {
a += b;
if (a >= mod) a -= mod;
if (a < 0) a += mod;
}
int st[N * 4];
int lz[N * 4];
void build(int id, int L, int R) {
if (R - L == 1) {
st[id] = mul[L + n];
return;
}
int mid = L + R >> 1;
build(id * 2, L, mid);
build(id * 2 + 1, mid, R);
st[id] = (st[id * 2] + st[id * 2 + 1]) % mod;
}
void push(int id, int val) {
if (!val) return;
st[id] = (mod - st[id]) % mod;
lz[id] ^= 1;
}
void update(int id, int L, int R, int u, int v) {
if (u >= R || L >= v) return;
if (u <= L && R <= v) {
push(id, 1);
return;
}
push(id * 2, lz[id]);
push(id * 2 + 1, lz[id]);
lz[id] = 0;
int mid = L + R >> 1;
update(id * 2, L, mid, u, v);
update(id * 2 + 1, mid, R, u, v);
st[id] = (st[id * 2] + st[id * 2 + 1]) % mod;
}
int get(int id, int L, int R, int u, int v) {
if (u >= R || L >= v) return 0;
if (u <= L && R <= v) return st[id];
push(id * 2, lz[id]);
push(id * 2 + 1, lz[id]);
lz[id] = 0;
int mid = L + R >> 1;
return (get(id * 2, L, mid, u, v) + get(id * 2 + 1, mid, R, u, v)) % mod;
}
void init(int N, int M, vector<int> P, vector<int> A) {
n = N, m = M;
for (int i = 1; i < n + m; ++i) g[P[i]].push_back(i);
mul[0] = 1;
dfs(0);
fix(0);
for (int i = 1; i < n + m; ++i) mul[i] = 1LL * mul[i] * mul[P[i]] % mod;
build(1, 0, m);
for (int i = 0; i < m; ++i) if (A[i]) add(ans, get(1, 0, m, i, i + 1)), update(1, 0, m, i, i + 1);
}
int count_ways(int L, int R) {
++R;
add(ans, get(1, 0, m, L - n, R - n));
update(1, 0, m, L - n, R - n);
return ans;
}
//
//int main() {
// int N, M, Q;
// assert(3 == scanf("%d %d %d", &N, &M, &Q));
// std::vector<int> P(N + M), A(M);
// for (int i = 0; i < N + M; ++i) {
// assert(1 == scanf("%d", &P[i]));
// }
// for (int j = 0; j < M; ++j) {
// assert(1 == scanf("%d", &A[j]));
// }
// init(N, M, P, A);
//
// for (int i = 0; i < Q; ++i) {
// int L, R;
// assert(2 == scanf("%d %d", &L, &R));
// printf("%d\n", count_ways(L, R));
// }
// return 0;
//}
