#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
#define vec vector
#define int long long
#define arr array
const int MX = 200'005;
vec<int32_t> a;
vec<int> tree[MX];
int tot[MX];
int n, m;
const int MXM = 100'005;
const int MOD = 1'000'002'022;
int contr[MXM];
struct SegLazy {
bool flip = false;
SegLazy merge(SegLazy other) {
return {flip ^ other.flip};
}
};
struct SegNode {
arr<int, 2> sums = {0, 0};
SegNode merge(SegNode other) {
return {{sums[0]+other.sums[0], sums[1]+other.sums[1]}};
}
SegNode upd(SegLazy lazy) {
if(lazy.flip) {
return {{sums[1], sums[0]}};
}
else {
return {{sums[0], sums[1]}};
}
}
};
struct SegTree {
int n;
vec<SegNode> data;
vec<SegLazy> lazy;
SegTree(int in) {
n = 1;
while(n < in) n *= 2;
data = vec<SegNode>(n*2);
lazy = vec<SegLazy>(n*2);
}
void pull(int i) {
data[i] = data[i*2].merge(data[i*2+1]);
}
void set(int i, SegNode val) {
i += n;
data[i] = val;
while(i > 1) {
i /= 2;
pull(i);
}
}
void push(int i) {
data[i] = data[i].upd(lazy[i]);
if(i*2 >= n*2) {
lazy[i] = {};
return;
}
lazy[i*2] = lazy[i*2].merge(lazy[i]);
lazy[i*2+1] = lazy[i*2+1].merge(lazy[i]);
lazy[i] = {};
}
void upd(int l, int r, SegLazy val) {
_upd(l, r, 1, 0, n, val);
}
void _upd(int l, int r, int ti, int tl, int tr, SegLazy val) {
//cerr << tl << ' ' << tr << '\n';
push(ti);
if(l >= tr || r <= tl) return;
if(l <= tl && r >= tr) {
lazy[ti] = val;
push(ti);
return;
}
int tm = (tl+tr)/2;
_upd(l, r, ti*2, tl, tm, val);
_upd(l, r, ti*2+1, tm, tr, val);
pull(ti);
}
};
SegTree st(0);
void dfs1(int u) {
if(u >= n) {
tot[u] = 1;
return;
}
tot[u] = tree[u].size();
for(int v : tree[u]) {
dfs1(v);
tot[u] *= tot[v];
tot[u] %= MOD;
}
}
void dfs2(int u, int top) {
if(u >= n) {
contr[u-n] = top;
return;
}
vec<int> pref_mul(tree[u].size()+1);
vec<int> suf_mul(tree[u].size()+1);
pref_mul[0] = 1;
suf_mul[0] =1;
for(int i = 0; i<tree[u].size(); i++) {
pref_mul[i+1] = pref_mul[i]*tot[tree[u][i]];
pref_mul[i+1] %= MOD;
suf_mul[i+1] = suf_mul[i]*tot[tree[u][tree[u].size()-i-1]];
suf_mul[i+1] %= MOD;
}
for(int i = 0; i<tree[u].size(); i++) {
dfs2(tree[u][i], (top*pref_mul[i]*suf_mul[tree[u].size()-i-1]) % MOD);
}
}
void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
n = N;
m = M;
a = A;
for(int i = 1; i<N+M; i++) {
tree[P[i]].push_back(i);
}
dfs1(0);
dfs2(0, 1);
st = SegTree(m);
for(int i = 0; i<m; i++) {
//cerr << contr[i] << ' ';
SegNode node = {{0, contr[i]}};
st.set(i, node);
st.upd(i, i+1, {A[i]});
}
//cerr << '\n';
//cerr << st.data[1].sums[0] << '\n';
}
int32_t count_ways(int32_t L, int32_t R) {
//cerr << "QUERY: " << L << ' ' << R << '\n';
st.upd(L-n, R+1-n, {true});
return st.data[1].sums[0] % MOD;
}
