#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
#define int long long
const int MXN = 2e5 + 5;
const int mod = 1e9 + 2022;
int n, m, res = 0;
vector<int> A, P;
vector<int> adj[MXN];
int dp[2][MXN], SZ[MXN];
int way[MXN];
void _init(int a)
{
if (adj[a].empty())
{
way[a] = 1;
return;
}
way[a] = adj[a].size();
for (int &v : adj[a])
{
_init(v);
way[a] = (way[a] * way[v]) % mod;
}
}
int val[MXN];
void dfs(int a, int cur)
{
if (adj[a].empty())
{
val[a] = cur;
return;
}
vector<int> pre(adj[a].size()), suf(adj[a].size());
for (int i = 0; i < adj[a].size(); i++)
{
pre[i] = (i ? pre[i - 1] : 1LL);
pre[i] = (pre[i] * way[adj[a][i]]) % mod;
}
for (int i = (int)adj[a].size() - 1; i >= 0; i--)
{
suf[i] = (i + 1 < adj[a].size() ? suf[i + 1] : 1LL);
suf[i] = (suf[i] * way[adj[a][i]]) % mod;
}
for (int i = 0; i < adj[a].size(); i++)
{
int A = (i ? pre[i - 1] : 1LL), B = (i + 1 < adj[a].size() ? suf[i + 1] : 1LL);
dfs(adj[a][i], (((cur * A) % mod) * B) % mod);
}
}
array<int, 2> st[MXN << 2];
int lz[MXN << 2];
void relax(int l, int r, int x)
{
if (!lz[x]) return;
swap(st[x][0], st[x][1]);
if (l == r)
{
lz[x] = 0;
return;
}
lz[2*x] ^= lz[x], lz[2*x + 1] ^= lz[x];
lz[x] = 0;
}
void upd(int l, int r, int x, int lx, int rx)
{
relax(l, r, x);
if (l > rx || r < lx) return;
if (l >= lx && r <= rx)
{
lz[x] ^= 1;
relax(l, r, x);
return;
}
int mid = (l + r) >> 1;
upd(l, mid, 2*x, lx, rx);
upd(mid + 1, r, 2*x + 1, lx, rx);
st[x][0] = (st[2*x][0] + st[2*x + 1][0]) % mod;
st[x][1] = (st[2*x][1] + st[2*x + 1][1]) % mod;
}
void build(int l, int r, int x)
{
if (l == r)
{
st[x][0] = A[l] * val[l];
st[x][1] = (A[l] ^ 1) * val[l];
return;
}
int mid = (l + r) >> 1;
build(l, mid, 2*x);
build(mid + 1, r, 2*x + 1);
st[x][0] = (st[2*x][0] + st[2*x + 1][0]) % mod;
st[x][1] = (st[2*x][1] + st[2*x + 1][1]) % mod;
}
void init(int32_t N, int32_t M, vector<int32_t> PP, vector<int32_t> AA)
{
n = N, m = M;
for (int32_t &i : PP) P.push_back(i);
for (int32_t &i : AA) A.push_back(i);
reverse(A.begin(), A.end());
A.resize(N + M, 0);
reverse(A.begin(), A.end());
for (int i = 1; i < N + M; i++) adj[P[i]].push_back(i);
_init(0);
dfs(0, 1);
build(N, N + M - 1, 1);
}
int32_t count_ways(int32_t L, int32_t R) {
upd(n, n + m - 1, 1, L, R);
return st[1][0];
}
