#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
const ll N = 2e5 + 5, mod = 1e9 + 2022;
vector<ll> g[N];
ll a[N], n, m, sub[N], p[N], val[N];
ll st[2][N << 2], lazy[N << 2];
void init(ll v)
{
sub[v] = max(1, (int)g[v].size());
for (ll to : g[v])
init(to), sub[v] = sub[v] * sub[to] % mod;
}
void dfs(ll v)
{
ll pref[g[v].size()], suf[g[v].size()];
for (ll i = 0; i < g[v].size(); i++)
pref[i] = (i == 0 ? 1 : pref[i - 1]) * sub[g[v][i]] % mod;
for (ll i = (int)g[v].size() - 1; i >= 0; i--)
suf[i] = (i + 1 < g[v].size() ? suf[i + 1] : 1) * sub[g[v][i]] % mod;
for (ll i = 0; i < g[v].size(); i++)
val[g[v][i]] = (i - 1 < 0 ? 1 : pref[i - 1]) * (i + 1 < g[v].size() ? suf[i + 1] : 1) % mod * val[v] % mod, dfs(g[v][i]);
}
void build(ll l, ll r, ll v)
{
if (l == r)
{
st[a[l + n]][v] = val[l + n];
return;
}
ll mid = (l + r) >> 1;
build(l, mid, v << 1);
build(mid + 1, r, v << 1 | 1);
for (ll i = 0; i < 2; i++)
st[i][v] = st[i][v << 1] + st[i][v << 1 | 1];
}
void push(ll v, ll l, ll r)
{
if (l != r and lazy[v])
{
swap(st[0][v << 1], st[1][v << 1]);
swap(st[0][v << 1 | 1], st[1][v << 1 | 1]);
lazy[v << 1] ^= 1;
lazy[v << 1 | 1] ^= 1;
lazy[v] = 0;
}
}
void modify(ll i, ll j, ll l, ll r, ll v)
{
if (max(i, l) > min(j, r))
return;
push(v, l, r);
if (i <= l and r <= j)
{
swap(st[0][v], st[1][v]);
lazy[v] ^= 1;
return;
}
ll mid = (l + r) >> 1;
modify(i, j, l, mid, v << 1);
modify(i, j, mid + 1, r, v << 1 | 1);
for (ll i = 0; i < 2; i++)
st[i][v] = st[i][v << 1] + st[i][v << 1 | 1];
}
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
n = N, m = M;
for (ll i = 1; i < n + m; i++)
g[p[i] = P[i]].push_back(i);
for (ll i = 0; i < m; i++)
a[i + n] = A[i];
init(0);
val[0] = 1;
dfs(0);
build(0, m - 1, 1);
}
int count_ways(int l, int r)
{
modify(l - n, r - n, 0, m - 1, 1);
return st[1][1];
}
