#include <bits/stdc++.h>
using namespace std;
const int mod = 1000002022;
const int N = 1e5+2;
const int NM = 2e5+2;
int n, m, val[NM], lazy[4*N], contrib[N];
vector<int>G[NM];
pair<int, int>aint[4*N];
pair<int, int>init_contrib[NM];
void dfs (int nod) {
if (nod >= n) {
val[nod] = 1;
return;
}
val[nod] = G[nod].size();
for (auto it : G[nod]) {
dfs(it);
val[nod] = 1ll * val[it] * val[nod] % mod;
}
}
void dfs_contrib (int nod, int c) {
if (nod >= n) {
contrib[nod - n] = c;
return;
}
vector<int>pref(G[nod].size());
vector<int>suf(G[nod].size());
for (int i = 0; i < G[nod].size(); i++) {
int child = G[nod][i];
pref[i] = val[child];
if (i)
pref[i] = 1ll * pref[i - 1] * pref[i] % mod;
}
for (int i = G[nod].size() - 1; i >= 0; i--) {
int child = G[nod][i];
suf[i] = val[child];
if (i + 1 < G[nod].size())
suf[i] = 1ll * suf[i] * suf[i + 1] % mod;
}
for (int i = 0; i < G[nod].size(); i++) {
int child = G[nod][i];
int val = c;
if (i > 0)
val = 1ll * val * pref[i - 1] % mod;
if (i + 1 < G[nod].size())
val = 1ll * val * suf[i + 1] % mod;
dfs_contrib(child, val);
}
}
pair<int, int> operator+ (pair<int, int> a, pair<int, int>b) {
return {(a.first + b.first) % mod, (a.second + b.second) % mod};
}
void build (int nod, int st, int dr) {
if (st == dr) {
aint[nod] = init_contrib[st];
return;
}
int mid = (st + dr) / 2;
build(2 * nod, st, mid);
build(2 * nod + 1, mid + 1, dr);
aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}
void push (int nod) {
if (!lazy[nod])
return;
for (int i = 0; i < 2; i++) {
swap(aint[2 * nod + i].first, aint[2 * nod + i].second);
lazy[2 * nod + i] ^= 1;
}
lazy[nod] = 0;
}
void update (int nod, int st, int dr, int a, int b) {
if (a <= st && dr <= b) {
swap(aint[nod].first, aint[nod].second);
lazy[nod] ^= 1;
return;
}
int mid = (st + dr) / 2;
push(nod);
if (a <= mid)
update(2 * nod, st, mid, a, b);
if (b > mid)
update(2 * nod + 1, mid + 1, dr, a, b);
aint[nod] = aint[2 * nod] + aint[2 * nod + 1];
}
void init (int _n, int _m, vector<int>P, vector<int> A) {
n = _n;
m = _m;
for (int i = 1; i < P.size(); i++)
G[P[i]].push_back(i);
dfs(0);
dfs_contrib(0, 1);
for (int i = 0; i < m; i++) {
pair<int, int>c = {0, contrib[i]};
if (!A[i])
swap(c.first, c.second);
init_contrib[i] = c;
}
build(1, 0, m - 1);
}
int count_ways(int l, int r) {
update(1, 0, m - 1, l - n, r - n);
return aint[1].second;
}
