#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int n, m;
const int maxn = 2e5 + 10;
const int mod = 1000002022;
vector<int> adj[maxn];
vector<ll> pref[maxn], suf[maxn], fator(maxn);
ll dfs_init( int cur ){
pref[cur].push_back(1);
suf[cur].push_back(1);
ll resp = max( (int)adj[cur].size(), 1 );
for( int viz : adj[cur] ){
ll tot = dfs_init( viz );
resp *= tot;
resp %= mod;
pref[cur].push_back(tot);
suf[cur].push_back(tot);
}
pref[cur].push_back(1);
suf[cur].push_back(1);
for( int i = 1; i < (int)pref[cur].size(); i++ ) pref[cur][i] = (pref[cur][i - 1]*pref[cur][i])%mod;
for( int i = (int)suf[cur].size() - 2; i >= 0; i-- ) suf[cur][i] = (suf[cur][i + 1]*suf[cur][i])%mod;
return resp;
}
void dfs( int cur ){
for( int i = 0; i < (int)adj[cur].size(); i++ ){
int viz = adj[cur][i];
fator[viz] = (((fator[cur]*pref[cur][i])%mod)*suf[cur][i + 2])%mod;
dfs( viz );
}
}
struct Node{
ll v1 = 0, v2 = 0;
bool lazy = false;
Node( ll v1 = 0, ll v2 = 0 ) : v1(v1), v2(v2) {}
Node operator + ( Node n ){
return Node( (v1 + n.v1)%mod, (v2 + n.v2)%mod );
}
} seg[4*maxn];
void build( int pos, int ini, int fim, vector<int> &a ){
if( ini == fim ){
seg[pos] = Node(fator[ini]*a[ini - n], fator[ini]*(1 - a[ini - n]) );
return;
}
int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
build( l, ini, mid, a ); build( r, mid + 1, fim, a );
seg[pos] = seg[l] + seg[r];
}
void refresh( int pos, int ini, int fim ){
if( !seg[pos].lazy ) return;
seg[pos].lazy = false;
swap( seg[pos].v1, seg[pos].v2 );
if( ini == fim ) return;
int l = 2*pos, r = 2*pos + 1;
seg[l].lazy ^= true;
seg[r].lazy ^= true;
}
void update( int pos, int ini, int fim, int ki, int kf ){
refresh( pos, ini, fim );
if( ki > fim || ini > kf ) return;
if( ki <= ini && fim <= kf ){
seg[pos].lazy = true; refresh( pos, ini, fim );
return;
}
int l = 2*pos, r = 2*pos + 1, mid = ( ini + fim )/2;
update( l, ini, mid, ki, kf ); update( r, mid + 1, fim, ki, kf );
seg[pos] = seg[l] + seg[r];
}
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);
dfs_init(0);
fator[0] = 1;
dfs(0);
build( 1, n, n + m - 1, A );
}
int count_ways(int l, int r) {
update( 1, n, n + m - 1, l, r );
return seg[1].v1;
}
