#include "circuit.h"
#include "bits/stdc++.h"
using namespace std;
#define forR(i, x) for(int i = 0; i < (x); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<bool> vb;
const ll MOD = 1000002022;
const int MN = 1e5 + 10;
vvi ch;
vll w;
int n, m;
vll totPos;
void sdfs(int c) {
totPos[c] = c >= n ? 1 : ch[c].size();
for(int i : ch[c]) {
sdfs(i);
totPos[c] = totPos[c] * totPos[i] % MOD;
}
}
void dfs(int c, ll cw) {
w[c] = cw;
vll ppa(ch[c].size()), spa(ch[c].size()), val(ch[c].size());
for(int j = 0; j < ch[c].size(); j++) {
val[j] = totPos[ch[c][j]];
ppa[j] = val[j] * (j == 0 ? 1 : ppa[j-1]) % MOD;
}
for(int j = (int) ch[c].size() - 1; j >= 0; --j) {
spa[j] = val[j] * (j + 1 == ch[c].size() ? 1 : spa[j+1]) % MOD;
}
for(int i = 0; i < ch[c].size(); ++i) {
ll wCh = cw * (i == 0 ? 1 : ppa[i-1]) % MOD * (i + 1 == ch[c].size() ? 1 : spa[i+1]) % MOD;
dfs(ch[c][i], wCh);
}
}
vb tgl;
struct node {
ll tot, iTot;
bool lz;
};
const int MM = 1e5 + 10, ME = 4 * MM;
node seg[ME];
void push(int c) {
if(seg[c].lz) {
if(2 * c + 1 < ME) {
swap(seg[2*c].tot, seg[2*c].iTot);
seg[2*c].lz = !seg[2*c].lz;
swap(seg[2*c+1].tot, seg[2*c+1].iTot);
seg[2*c+1].lz = !seg[2*c+1].lz;
}
seg[c].lz = false;
}
}
void build(int v, int nl, int nr) {
if(nl == nr) {
if(tgl[nl + n]) seg[v].tot = w[nl+n], seg[v].iTot = 0;
else seg[v].tot = 0, seg[v].iTot = w[nl+n];
} else {
int mid = (nl+nr)/2;
build(2*v, nl, mid);
build(2*v+1, mid+1, nr);
seg[v].tot = (seg[2*v].tot+seg[2*v+1].tot) % MOD;
seg[v].iTot = (seg[2*v].iTot+seg[2*v+1].iTot) % MOD;
}
}
void upd(int v, int nl, int nr, int l, int r) {
push(v);
if(l > r) return;
if(l == nl && r == nr) {
swap(seg[v].tot, seg[v].iTot);
assert(!seg[v].lz);
seg[v].lz = true;
} else {
int mid = (nl+nr)/2;
upd(2*v, nl, mid, l, min(mid, r));
upd(2*v+1, mid+1, nr, max(mid+1,l), r);
seg[v].tot = (seg[2*v].tot + seg[2*v+1].tot) % MOD;
seg[v].iTot = (seg[2*v].iTot + seg[2*v+1].iTot) % MOD;
}
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
::n = N, ::m = M;
ch.resize(N+M);
totPos.resize(N+M);
w.resize(N+M);
tgl.resize(N+M);
REP(i, 1, N+M) ch[P[i]].push_back(i);
sdfs(0);
dfs(0, 1);
forR(i, M) tgl[N+i] = A[i] == 1;
build(1, 0, m-1);
}
int count_ways(int L, int R) {
upd(1, 0, m-1, L-n, R-n);
ll tot = seg[1].tot;
return (int) tot;
}
