#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define X first
#define Y second
#define lc id<<1
#define rc lc|1
#define mid ((l+r)>>1)
const int MXN=2e5+5, MOD = 1000002022;
int n, m;
ll dp[MXN];
vector<int> g[MXN];
void dfs1(int v) {
if(v>=n) {
dp[v] = 1;
return;
}
dp[v] = g[v].size();
for(int u : g[v]) {
dfs1(u);
dp[v] = dp[v]*dp[u]%MOD;
}
}
pll seg[MXN<<2];
bool lz[MXN<<2];
inline ll md(ll x) { return x - (x>=MOD ? MOD : 0); }
pll operator+(pll x, pll y) { return {md(x.X+y.X), md(x.Y+y.Y)}; }
void modify(int p, pll x, int l=0, int r=m, int id=1) {
if(r-l == 1) {
seg[id] = x;
return;
}
p<mid ? modify(p, x, l, mid, lc) : modify(p, x, mid, r, rc);
seg[id] = seg[lc] + seg[rc];
}
inline void apply(int id) {
swap(seg[id].X, seg[id].Y);
lz[id] ^= 1;
}
inline void push(int id) {
if(lz[id]) {
apply(lc);
apply(rc);
lz[id] = 0;
}
}
void upd(int s, int e, int l=0, int r=m, int id=1) {
if(s>=r || l>=e) return;
if(s<=l && r<=e) {
apply(id);
return;
}
push(id);
upd(s, e, l, mid, lc);
upd(s, e, mid, r, rc);
seg[id] = seg[lc] + seg[rc];
}
vector<int> A;
void dfs2(int v, ll cur=1) {
if(v>=n) return modify(v-n, A[v-n] ? pll(cur, 0) : pll(0, cur));
vector<ll> pre(g[v].size()), suf(g[v].size());
pre[0] = 1;
for(int i=1; i<g[v].size(); i++)
pre[i] = pre[i-1]*dp[g[v][i-1]]%MOD;
suf[(int)g[v].size()-1] = 1;
for(int i=(int)g[v].size()-2; i>=0; i--)
suf[i] = suf[i+1]*dp[g[v][i+1]]%MOD;
for(int i=0; i<g[v].size(); i++)
dfs2(g[v][i], cur*pre[i]%MOD*suf[i]%MOD);
}
void init(int N, int M, vector<int> P, vector<int> A) {
n = N;
m = M;
::A = A;
for(int i=1; i<N+M; i++)
g[P[i]].push_back(i);
dfs1(0);
dfs2(0);
}
int count_ways(int L, int R) {
upd(L-n, R-n+1);
return seg[1].X;
}
