#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MOD 1000002022ll
#define MAX 201010
int N, M;
vector<int> adj[MAX], prt;
vector<ll> psum[MAX], ssum[MAX];
ll A[MAX];
ll ma[MAX];
ll mulall[MAX];
vector<int> ison;
ll f(ll& a) { a %= MOD, a += MOD, a %= MOD; return a; }
struct segtree {
vector<ll> tree, sum;
vector<int> lazy;
void init(int s, int e, int ind) {
if (s == e) {
sum[ind] = mulall[s];
if (ison[s]) tree[ind] = mulall[s];
return;
}
int m = (s + e) >> 1;
init(s, m, ind * 2);
init(m + 1, e, ind * 2 + 1);
sum[ind] = sum[ind * 2] + sum[ind * 2 + 1];
f(sum[ind]);
tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
f(tree[ind]);
}
segtree(int N = 0) {
tree.resize(N * 4);
lazy.resize(N * 4);
sum.resize(N * 4);
}
void prop(int ind) {
if (lazy[ind]) {
for (auto c : { ind * 2, ind * 2 + 1 }) tree[c] = sum[c] - tree[c], f(tree[c]), lazy[c] ^= 1;
lazy[ind] = 0;
}
}
void upd(int s, int e, int l, int r, int ind = 1) {
if (e < l || r < s) return;
if (s != e) prop(ind);
if (l <= s && e <= r) {
tree[ind] = sum[ind] - tree[ind];
f(tree[ind]);
lazy[ind] ^= 1;
return;
}
int m = (s + e) >> 1;
upd(s, m, l, r, ind * 2);
upd(m + 1, e, l, r, ind * 2 + 1);
tree[ind] = tree[ind * 2] + tree[ind * 2 + 1];
f(tree[ind]);
}
ll get() { return tree[1]; }
};
void dfs(int x) {
A[x] = 1;
ma[x] = 1;
if (x >= N) {
return;
}
psum[x].resize(adj[x].size());
ssum[x].resize(adj[x].size());
int i;
for (i = 0; i < adj[x].size(); i++) {
int v = adj[x][i];
dfs(v);
psum[x][i] = ssum[x][i] = A[v];
A[x] *= A[v];
A[x] %= MOD;
}
A[x] *= adj[x].size();
f(A[x]);
int c = adj[x].size();
for (i = 1; i < c; i++) psum[x][i] *= psum[x][i - 1], f(psum[x][i]);
for (i = c - 2; i >= 0; i--) ssum[x][i] *= ssum[x][i + 1], f(ssum[x][i]);
for (i = 0; i < c; i++) {
ll mul = 1;
if (i > 0) mul *= psum[x][i - 1], f(mul);
if (i < c - 1) mul *= ssum[x][i + 1], f(mul);
ma[adj[x][i]] *= mul;
f(ma[adj[x][i]]);
}
}
void calc(int x, ll d) {
d *= ma[x];
d %= MOD;
if (x >= N) mulall[x - N + 1] = d;
for (auto v : adj[x]) calc(v, d);
}
segtree seg;
void init(int _N, int _M, std::vector<int> _P, std::vector<int> A) {
prt = _P;
N = _N;
M = _M;
for (int i = 1; i < N + M; i++) adj[prt[i]].push_back(i);
dfs(0);
calc(0, 1);
ison = A;
ison.insert(ison.begin(), 0);
seg = segtree(M);
seg.init(1, M, 1);
}
int count_ways(int L, int R) {
L -= N - 1;
R -= N - 1;
seg.upd(1, M, L, R);
return seg.get();
}
