#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;
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;
}
void Flip(int u) {
if (c[u]) add(ans, - mul[u]);
else add(ans, mul[u]);
c[u] ^= 1;
}
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);
memset(c, 0, sizeof(c));
for (int i = 1; i < n + m; ++i) mul[i] = 1LL * mul[i] * mul[P[i]] % mod;
for (int i = 0; i < m; ++i) if (A[i]) Flip(i + n);
}
int count_ways(int L, int R) {
for (int i = L; i <= R; ++i) Flip(i);
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;
//}
