#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 pi = pair<int, int>;
using ti = tuple<int, int, int>;
using Adj = V<vi>;
using vvi = V<vi>;
#include "circuit.h"
const int M = 1'000'002'022;
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;
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);
f0r(i, m) if (A[i]) ans = (ans + ways[n+i]) % M;
}
int count_ways(int L, int R) {
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 ans;
}
