#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define f0r(i, n) for (auto i = 0; i < (n); ++i)
#define fnr(i, n, k) for (auto i = (n); i < (k); ++i)
#define all(v) (v).begin(), (v).end()
#define pb push_back
#define F first
#define S second
#define ctn(x) cout << x << '\n'
#define forl(a, l) for (auto a : l)
#define ctl(l) for (auto &a : (l)) cout << a << ' '; cout << endl;
#define lb(v, x) (lower_bound(all(v), x) - begin(v))
#define ub(v, x) (upper_bound(all(v), x) - begin(v))
#define pq priority_queue
template <class T>
using V = vector<T>;
using ll = long long;
using vi = V<int>;
using vl = V<ll>;
using pl = pair<ll, ll>;
using ti = tuple<int, int, int>;
using Adj = V<vi>;
using vvi = V<vi>;
#include "circuit.h"
const int M = 1'000'002'022;
inline pl merge(pl p1, pl p2) {
return {(p1.F+p2.F) % M, (p1.S+p2.S) % M};
}
struct ST {
int N;
vi lzy;
V<pl> tr;
ST() {}
ST(V<pl> &A) {
int n = A.size();
for (N=1; N<n; N*=2);
lzy.resize(2*N);
tr.resize(2*N);
f0r(i, n) {
tr[N+i] = A[i];
}
for (int i = N-1; i; --i) {
tr[i] = merge(tr[2*i], tr[2*i+1]);
}
}
void apply(int v, int x) {
if (x) swap(tr[v].F, tr[v].S);
lzy[v] ^= x;
}
void push_down(int v) {
apply(2*v, lzy[v]);
apply(2*v+1, lzy[v]);
}
#define m (l+r)/2
void upd(int ql, int qr, int v, int l, int r) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) {
apply(v, 1);
return;
}
push_down(v);
upd(ql, qr, 2*v, l, m);
upd(ql, qr, 2*v+1, m+1, r);
tr[v] = merge(tr[2*v], tr[2*v+1]);
}
#undef m
void upd(int ql, int qr) {
upd(ql, qr, 1, 0, N-1);
}
};
vl ways, prod;
Adj G;
vi P, A, sz;
void dfs(int v) {
sz[v] = 1;
prod[v] = 1;
if (!G[v].size()) return;
forl(c, G[v]) {
dfs(c);
prod[v] = (prod[v] * prod[c]) % M;
sz[v] += sz[c];
}
prod[v] = (prod[v] * (G[v].size())) % M;
}
void dfs2(int v) {
int n = G[v].size();
if (!n) return;
vl pf(n), sf(n);
pf[0] = sf[n-1] = 1;
fnr(i, 1, n) {
pf[i] = (pf[i-1] * prod[G[v][i-1]]) % M;
}
for (int i = n-2; i >= 0; --i) {
sf[i] = (sf[i+1] * prod[G[v][i+1]]) % M;
}
f0r(i, n) {
ways[G[v][i]] = (((ways[v] * pf[i]) % M) * sf[i]) % M;
dfs2(G[v][i]);
}
}
ll ans = 0;
int N;
ST st;
void init(int n, int m, std::vector<int> p, std::vector<int> a) {
N=n;
int t = n+m;
G = Adj(t);
fnr(i, 1, t) G[p[i]].pb(i);
ways = prod = vl(t);
ways[0] = 1;
sz = vi(t);
P = p, A = a;
ans = 0;
dfs(0);
dfs2(0);
V<pl> val(m);
f0r(i, m) {
val[i] = {a[i] * ways[n+i], !a[i] * ways[n+i]};
}
st = ST(val);
//f0r(i, m) if (A[i]) ans = (ans + ways[n+i]) % M;
}
int count_ways(int L, int R) {
st.upd(L-N, R-N);
//for (int i = L; i <= R; ++i) {
// if (A[i-N]) ans = (((ans - ways[i]) % M) + M) % M;
// else ans = (ans + ways[i]) % M;
// A[i-N] ^= 1;
//}
return st.tr[1].F;
}
