#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
const int MOD = 1e9 + 2022;
struct Segtree {
int n;
vector<array<int, 2>> a;
vector<int> lazy;
void init(int _n, const vector<array<int, 2>> &val) {
n = _n;
a.assign(4 * n + 1, {0, 0});
lazy.assign(4 * n + 1, 0);
build(1, 0, n - 1, val);
}
void build(int id, int l, int r, const vector<array<int, 2>> &val) {
if (l == r) {
a[id] = val[l];
cerr << "build " << a[id][0] << ' ' << a[id][1] << endl;
return;
}
int mid = (l + r) >> 1;
build(id << 1, l, mid, val);
build(id << 1 | 1, mid + 1, r, val);
a[id][0] = (a[id << 1][0] + a[id << 1 | 1][0]) % MOD;
a[id][1] = (a[id << 1][1] + a[id << 1 | 1][1]) % MOD;
}
void doLazy(int id, int l, int r) {
if (lazy[id]) {
swap(a[id][0], a[id][1]);
if (l < r) {
lazy[id << 1] ^= lazy[id];
lazy[id << 1 | 1] ^= lazy[id];
}
lazy[id] = 0;
}
}
void update(int id, int l, int r, int u, int v) {
doLazy(id, l, r);
if (v < l || r < u) {
return;
}
if (u <= l && r <= v) {
lazy[id] ^= 1;
doLazy(id, l, r);
return;
}
int mid = (l + r) >> 1;
update(id << 1, l, mid, u, v);
update(id << 1 | 1, mid + 1, r, u, v);
a[id][0] = (a[id << 1][0] + a[id << 1 | 1][0]) % MOD;
a[id][1] = (a[id << 1][1] + a[id << 1 | 1][1]) % MOD;
}
void update(int l, int r) {
update(1, 0, n - 1, l, r);
}
void debug(int id, int l, int r) {
doLazy(id, l, r);
if (l == r) {
return;
}
int mid = (l + r) >> 1;
debug(id << 1, l, mid);
debug(id << 1 | 1, mid + 1, r);
}
int get() {
doLazy(1, 0, n - 1);
return a[1][0];
}
} ST;
int n, m, c[N], f[N];
vector<int> childs[N];
void dfs1(int u) {
if (childs[u].empty()) {
c[u] = 1;
return;
}
c[u] = childs[u].size();
for (int v : childs[u]) {
dfs1(v);
c[u] = 1ll * c[u] * c[v] % MOD;
}
}
void dfs2(int u) {
if (childs[u].empty()) {
return;
}
int n = childs[u].size();
vector<int> l(n), r(n);
l[0] = 1;
for (int i = 1; i < n; ++i) {
l[i] = 1ll * l[i - 1] * c[childs[u][i - 1]] % MOD;
}
r[n - 1] = 1;
for (int i = n - 2; i >= 0; --i) {
r[i] = 1ll * r[i + 1] * c[childs[u][i + 1]] % MOD;
}
for (int i = 0; i < n; ++i) {
int v = childs[u][i];
f[v] = 1ll * l[i] * r[i] % MOD;
dfs2(v);
}
}
void dfs3(int u) {
for (int v : childs[u]) {
f[v] = 1ll * f[v] * f[u] % MOD;
dfs3(v);
}
}
void init(int _n, int _m, vector<int> p, vector<int> a) {
n = _n;
m = _m;
for (int i = 1; i < m + n; ++i) {
childs[p[i]].push_back(i);
}
dfs1(0);
fill(f, f + N, 1);
dfs2(0);
dfs3(0);
vector<array<int, 2>> val;
for (int i = n; i < m + n; ++i) {
if (a[i - n] == 1) {
val.push_back({f[i], 0});
} else {
val.push_back({0, f[i]});
}
}
ST.init(m, val);
}
int count_ways(int l, int r) {
ST.update(l - n, r - n);
return ST.get();
}
