#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//#define int ll
#include "circuit.h"
ll n,m,mod=1000002022;
vector<ll> roads[200005];
ll comb[200005],val[200005],pref[200005],suff[200005];
map<ll,ll> todfs[200005];
ll sumi[800005],segtree[800005];
ll lazy[800005];
void build(ll node, ll l, ll r){
if(l==r){
sumi[node] = val[l];
}
else{
ll mid = (l+r)/2;
build(node*2,l,mid);
build(node*2+1,mid+1,r);
sumi[node] = sumi[node*2]+sumi[node*2+1];
sumi[node] %= mod;
}
}
void pushdown(ll node, ll l, ll r){
if(lazy[node]){
segtree[node] = sumi[node]-segtree[node];
segtree[node] += mod;
segtree[node] %= mod;
if(l!=r){
lazy[node*2] ^= 1;
lazy[node*2+1] ^= 1;
}
lazy[node] = 0;
}
}
void update(ll node, ll l, ll r, ll needl, ll needr){
pushdown(node,l,r);
if(l>needr or r<needl){
return;
}
else if(l>=needl and r<=needr){
lazy[node] ^= 1;
pushdown(node,l,r);
}
else{
ll mid = (l+r)/2;
update(node*2,l,mid,needl,needr);
update(node*2+1,mid+1,r,needl,needr);
pushdown(node*2,l,mid);
pushdown(node*2+1,mid+1,r);
segtree[node] = segtree[node*2]+segtree[node*2+1];
segtree[node] %= mod;
}
}
void dfs1(ll x){
comb[x] = 1;
if(x>=n){
return;
}
for(ll i:roads[x]){
dfs1(i);
comb[x] *= comb[i];
comb[x] %= mod;
}
comb[x] *= roads[x].size();
comb[x] %= mod;
}
void dfs2(ll x, ll c){
if(x>=n){
val[x] = c;
return;
}
pref[0] = 1;
for(ll i=1;i<=roads[x].size();i++){
pref[i] = comb[roads[x][i-1]]*pref[i-1];
pref[i] %= mod;
}
suff[roads[x].size()+1] = 1;
for(ll i=roads[x].size();i>=1;i--){
suff[i] = comb[roads[x][i-1]]*suff[i+1];
suff[i] %= mod;
}
for(ll i=1;i<=roads[x].size();i++){
todfs[x][roads[x][i-1]] = (((pref[i-1]*suff[i+1])%mod)*c)%mod;
}
for(ll i:roads[x]){
dfs2(i,todfs[x][i]);
}
}
void init(int N, int M, vector<int> p, vector<int> a){
n = N;
m = M;
for(ll i=1;i<=n+m-1;i++){
roads[p[i]].push_back(i);
}
dfs1(0);
dfs2(0,1);
build(1,0,n+m-1);
for(ll i=0;i<a.size();i++){
if(a[i]){
update(1,0,n+m-1,i+n,i+n);
}
}
}
int count_ways(int l, int r){
update(1,0,n+m-1,l,r);
return segtree[1];
}
