#include "circuit.h"
#include <vector>
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
using namespace std;
#define ll long long
#define pll pair<ll,ll>
#define fs first
#define sc second
const int mxn = 2e5+10;
const ll mod = 1000002022;
vector<int> tree[mxn];
int par[mxn];
int N,M;
ll dp[mxn];
ll sz[mxn];
ll arr[mxn];
ll mad(ll a,ll b){
a += b;
return a>=mod?a-mod:a;
}
ll mub(ll a,ll b){
return mad(a,mod-b);
}
struct SEG{
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
ll seg[mxn*4][2];
int tag[mxn*4];
void push(int now,int l,int r){
if(!tag[now])return;
tag[ls] ^= 1;
tag[rs] ^= 1;
tag[now] = 0;
swap(seg[ls][0],seg[ls][1]);
swap(seg[rs][0],seg[rs][1]);
return;
}
void build(int now,int l,int r){
if(l == r){
seg[now][arr[l]] = dp[l];
return;
}
build(ls,l,mid);
build(rs,mid+1,r);
seg[now][0] = mad(seg[ls][0],seg[rs][0]);
seg[now][1] = mad(seg[ls][1],seg[rs][1]);
}
void modify(int now,int l,int r,int s,int e){
if(l>=s&&e>=r){
swap(seg[now][0],seg[now][1]);
tag[now] ^= 1;
return;
}
push(now,l,r);
if(mid>=s)modify(ls,l,mid,s,e);
if(mid<e)modify(rs,mid+1,r,s,e);
seg[now][0] = mad(seg[ls][0],seg[rs][0]);
seg[now][1] = mad(seg[ls][1],seg[rs][1]);
}
ll getval(){
return seg[0][1];
}
};
SEG seg;
void dfs(int now){
dp[now] = sz[now] = 1;
for(auto nxt:tree[now]){
dfs(nxt);
sz[now] = sz[nxt]*sz[now]%mod;
}
if(tree[now].size())sz[now] = sz[now]*tree[now].size()%mod;
return;
}
void dfs1(int now){
vector<ll> suf;
for(auto nxt:tree[now]){
suf.push_back(sz[nxt]);
}
suf.push_back(1);
for(int i = (int)suf.size()-2;i>=0;i--)suf[i] = suf[i+1]*suf[i]%mod;
ll pref = 1;
for(int i = 0;i<tree[now].size();i++){
int nxt = tree[now][i];
ll ts = pref*suf[i+1]%mod;
dp[nxt] = dp[now]*ts%mod;
dfs1(nxt);
pref = pref*sz[nxt]%mod;
}
return;
}
void init(int N1, int M1, std::vector<int> P, std::vector<int> A) {
N = N1,M = M1;
for(int i = 1;i<N+M;i++){
par[i] = P[i];
tree[par[i]].push_back(i);
}
for(int i = 0;i<M;i++){
arr[i+N] = A[i];
}
dfs(0);
dfs1(0);
seg.build(0,N,N+M-1);
/*
cerr<<"SZ: ";
for(int i = 0;i<N+M;i++)cerr<<sz[i]<<' ';cerr<<endl;
cerr<<"DP: ";
for(int i = 0;i<N+M;i++)cerr<<dp[i]<<' ';cerr<<endl;
*/
//for(int i = 0;i<N+M;i++)cerr<<dp[i][0]<<','<<dp[i][1]<<' ';cerr<<endl;
}
int count_ways(int L, int R) {
seg.modify(0,N,N+M-1,L,R);
//cerr<<"NOW: ";for(int i = N;i<N+M;i++)cerr<<arr[i]<<' ';cerr<<endl;
return seg.getval();
//dfs(0);
//cerr<<"NOW: ";
//for(int i = N;i<N+M;i++)cerr<<(dp[i][0]?0:1);cerr<<endl;
}
