#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 200005;
const ll mod = 1'000'002'022;
vector<int> adj[MAXN];
ll sbt[MAXN], lv[MAXN]; bool st[MAXN];
struct node{
int s, e, m; ll v0, v1; bool lazy;
node *l, *r;
node (int _s, int _e){
s = _s, e = _e, m = (s + e) >> 1, v0 = 0, v1 = 0, lazy = 0;
if (s == e) (st[s] ? v1 : v0) = lv[s];
else{
l = new node(s, m); r = new node(m + 1, e);
v0 = l->v0 + r->v0; v1 = l->v1 + r->v1;
}
}
void push(){
swap(v0, v1); lazy = !lazy;
}
void propo(){
if (s == e) return;
if (lazy){
l->push(); r->push();
lazy = 0;
}
}
void update(int x, int y){
if (x == s && y == e){
push(); return;
}
propo();
if (y <= m) l->update(x, y);
else if (x > m) r->update(x, y);
else{
l->update(x, m); r->update(m + 1, y);
}
propo();
v0 = l->v0 + r->v0; v1 = l->v1 + r->v1;
}
} *root;
void dfs(int x){
sbt[x] = max(1, (int)(adj[x].size()));
for (auto nn : adj[x]){
dfs(nn); sbt[x] = sbt[x] * sbt[nn] % mod;
}
}
void dfs2(int x, ll uv){
int asz = adj[x].size();
vector<ll> lp(asz + 2), rp(asz + 2);
lp[0] = 1; rp[asz + 1] = 1;
for (int i = 1; i <= asz; i++) lp[i] = lp[i - 1] * sbt[adj[x][i - 1]] % mod;
for (int i = asz; i >= 1; i--) rp[i] = rp[i + 1] * sbt[adj[x][i - 1]] % mod;
for (int i = 1; i <= asz; i++){
int nn = adj[x][i - 1]; dfs2(nn, uv * lp[i - 1] % mod * rp[i + 1] % mod);
}
lv[x] = uv;
}
void init(int N, int M, vector<int> P, vector<int> A) {
int tot = N + M;
for (int i = 1; i < tot; i++) adj[P[i]].push_back(i);
for (int i = N; i < tot; i++) st[i] = A[i - N];
dfs(0); dfs2(0, 1);
root = new node(N, tot - 1);
}
int count_ways(int L, int R) {
root->update(L, R);
return root->v1 % mod;
}
