#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD = 1'000'002'022;
const int MAXN = 2e5;
vector <int> adj[MAXN+5];
ll dp[MAXN+5], prod[MAXN+5], N, M;
struct Segtree {
ll l, r, flip, val;
Segtree *lf, *rg;
bool z = 0;
void build() {
val = flip = 0;
if (l == r) {
flip = dp[l];
}
else {
ll mid = (l+r)/2;
lf = new Segtree(), rg = new Segtree();
lf->l = l, lf->r = mid;
rg->l = mid+1, rg->r = r;
lf->build(), rg->build();
flip = (lf->flip+rg->flip)%MOD;
}
}
void push() {
if (z) {
lf->val = (lf->flip-lf->val+MOD)%MOD;
rg->val = (rg->flip-rg->val+MOD)%MOD;
lf->z ^= 1, rg->z ^= 1;
}
z = 0;
}
void update(ll x, ll y) {
if (l > y || r < x) return;
if (l >= x && r <= y) {
val = (flip-val+MOD)%MOD;
z ^= 1;
return;
}
push();
lf->update(x, y), rg->update(x, y);
val = (lf->val+rg->val)%MOD;
}
} sg;
void dfs2(ll idx) {
if (idx >= N) return;
vector <ll> sf((ll)adj[idx].size()+1, 1LL);
for (int i = (ll)adj[idx].size()-1; i >= 0; --i) {
sf[i] = sf[i+1]*prod[adj[idx][i]]%MOD;
}
ll ps = 1;
for (int i = 0; i < (ll)adj[idx].size(); i++) {
dp[adj[idx][i]] = dp[idx]*ps%MOD*sf[i+1]%MOD;
dfs2(adj[idx][i]);
ps *= prod[adj[idx][i]];
ps %= MOD;
}
}
void dfs(ll idx) {
prod[idx] = 1;
for (auto i : adj[idx]) {
dfs(i);
prod[idx] *= prod[i];
prod[idx] %= MOD;
}
if (!adj[idx].empty()) {
prod[idx] *= (ll)adj[idx].size();
prod[idx] %= MOD;
}
}
void init(int n, int m, vector<int> P, vector<int> A) {
N = n, M = m;
for (int i = 1; i < N+M; i++) {
adj[P[i]].push_back(i);
}
// calculate the contribution of each source gate
dfs(0);
dp[0] = 1;
dfs2(0);
sg.l = N, sg.r = N+M-1;
sg.build();
for (int i = 0; i < M; i++) {
if (A[i]) sg.update(N+i, N+i);
}
}
int count_ways(int L, int R) {
sg.update(L, R);
return sg.val;
}
