#include <bits/stdc++.h>
using namespace std;
using ll = long long;
static const ll MOD = 1000002022;
static int gN, gM;
static vector<int> parentArr;
static vector<vector<int>> children;
static vector<ll> Sval;
static vector<ll> Wval;
static vector<ll> upVal;
static vector<ll> coef;
static vector<int> leafState;
struct SegTree
{
int n;
struct Node
{
ll sum;
ll totCoef;
bool flip;
};
vector<Node> st;
SegTree(int _n = 0) : n(_n)
{
if (n > 0)
st.resize(4 * n);
}
void build(int p, int l, int r)
{
if (l == r)
{
st[p].totCoef = coef[l] % MOD;
st[p].sum = (coef[l] * leafState[l]) % MOD;
st[p].flip = false;
return;
}
int m = (l + r) >> 1;
build(p << 1, l, m);
build(p << 1 | 1, m + 1, r);
st[p].totCoef = (st[p << 1].totCoef + st[p << 1 | 1].totCoef) % MOD;
st[p].sum = (st[p << 1].sum + st[p << 1 | 1].sum) % MOD;
st[p].flip = false;
}
inline void applyFlip(int p)
{
st[p].sum = (st[p].totCoef - st[p].sum) % MOD;
if (st[p].sum < 0) st[p].sum += MOD;
st[p].flip = !st[p].flip;
}
inline void push(int p)
{
if (!st[p].flip) return;
applyFlip(p << 1);
applyFlip(p << 1 | 1);
st[p].flip = false;
}
void updateRange(int p, int l, int r, int i, int j)
{
if (j < l || i > r) return;
if (l >= i && r <= j)
{
applyFlip(p);
return;
}
push(p);
int m = (l + r) >> 1;
updateRange(p << 1, l, m, i, j);
updateRange(p << 1 | 1, m + 1, r, i, j);
st[p].sum = (st[p << 1].sum + st[p << 1 | 1].sum) % MOD;
}
void init_build(int _n)
{
n = _n;
st.resize(4 * n);
build(1, 0, n - 1);
}
void invertInterval(int L, int R)
{
updateRange(1, 0, n - 1, L, R);
}
ll queryAll() const
{
return st[1].sum;
}
};
static SegTree seg;
void init(int N, int M, std::vector <int> P, std::vector <int> A)
{
gN = N;
gM = M;
parentArr.resize(N + M);
for (int i = 0; i < N + M; i++)
{
parentArr[i] = P[i];
}
children.assign(N + M, {});
for (int i = 1; i < N + M; i++)
{
int p = parentArr[i];
children[p].push_back(i);
}
leafState.resize(M);
for (int i = 0; i < M; i++)
{
leafState[i] = A[i];
}
Sval.assign(N + M, 0LL);
for (int v = N + M - 1; v >= 0; v--)
{
if (v >= N)
{
// Leaf
Sval[v] = 1;
}
else
{
ll prod = 1;
int d = (int)children[v].size();
for (int c : children[v])
{
prod = (prod * Sval[c]) % MOD;
}
prod = (prod * d) % MOD;
Sval[v] = prod;
}
}
Wval.assign(N + M, 1LL);
for (int v = 0; v < N; v++)
{
int d = (int)children[v].size();
if (d == 0) continue;
vector<ll> pref(d), suf(d);
for (int i = 0; i < d; i++)
{
pref[i] = Sval[children[v][i]];
suf[i] = pref[i];
}
for (int i = 1; i < d; i++)
{
pref[i] = (pref[i] * pref[i - 1]) % MOD;
}
for (int i = d - 2; i >= 0; i--)
{
suf[i] = (suf[i] * suf[i + 1]) % MOD;
}
for (int i = 0; i < d; i++)
{
ll left = (i > 0 ? pref[i - 1] : 1LL);
ll right = (i + 1 < d ? suf[i + 1] : 1LL);
ll w = (left * right) % MOD;
int c = children[v][i];
Wval[c] = w;
}
}
Wval[0] = 1;
upVal.assign(N + M, 1LL);
vector<int> bfs;
bfs.reserve(N + M);
bfs.push_back(0);
for (int idx = 0; idx < (int)bfs.size(); idx++)
{
int v = bfs[idx];
for (int c : children[v])
{
upVal[c] = (upVal[v] * Wval[c]) % MOD;
bfs.push_back(c);
}
}
coef.assign(M, 0LL);
for (int i = 0; i < M; i++)
{
coef[i] = upVal[N + i];
}
seg = SegTree(M);
seg.init_build(M);
}
int count_ways(int L, int R)
{
int l = L - gN;
int r = R - gN;
seg.invertInterval(l, r);
ll ans = seg.queryAll() % MOD;
return int(ans);
}
