#include "circuit.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define ll long long
const int N=1e5+500;
const ll mod=1000002022;
ll Puta(ll a,ll b){a%=mod,b%=mod;ll x=a*b;x%=mod;return x;}
ll Plus(ll a,ll b){a%=mod,b%=mod;ll x=a+b;x%=mod;return x;}
vector<int>E[2*N+500];
int a[N+500],n,m,P[2*N+500];
ll res[N+500],dp[2*N+500][2],F[2*N+500],F1[2*N+500];
void DFSsetup(int u){
if(E[u].empty()) return;
F[u]=E[u].size();
for(auto i:E[u]){
DFSsetup(i);
F[u]=Puta(F[u],F[i]);
}
for(auto i:E[u]){
F1[i]=1;
for(auto j:E[u]){
if(j!=i) F1[i]=Puta(F1[i],F[j]);
}
}
}
void DFS(int u){
if(E[u].empty()) return;
for(auto i:E[u]) DFS(i);
dp[u][1]=0;
for(auto i:E[u]) dp[u][1]=Plus(dp[u][1],Puta(dp[i][1],F1[i]));
//printf("%i: %lld %lld\n",u,dp[u][1],F[u]);
/*int mask=0;
while(mask< (1<<(E[u].size()))){
ll temp1=1,sum=0;
for(int i=0,temp=mask;i<E[u].size();i++,temp/=2){
temp1=Puta(temp1,dp[E[u][i]][temp%2]);sum+=temp%2;
}
if(mask!=0) dp[u][1]=Plus(dp[u][1],Puta(sum,temp1));
dp[u][0]=Plus(dp[u][0],Puta(E[u].size()-sum,temp1));
mask++;
}*/
//dp[u][0]=F[u]-dp[u][1];
}
void Update(int v){
dp[v][1]=1-dp[v][1];
dp[v][0]=1-dp[v][0];
int u=P[v];
while(u!=-1){
dp[u][1]=0;
for(auto i:E[u]) dp[u][1]=Plus(dp[u][1],Puta(dp[i][1],F1[i]));
/*dp[u][1]=dp[u][0]=0;
int mask=0;
while(mask< (1<<(E[u].size()))){
ll temp1=1,sum=0;
for(int i=0,temp=mask;i<E[u].size();i++,temp/=2){
temp1=Puta(temp1,dp[E[u][i]][temp%2]);sum+=temp%2;
}
if(mask!=0) dp[u][1]=Plus(dp[u][1],Puta(sum,temp1));
dp[u][0]=Plus(dp[u][0],Puta(E[u].size()-sum,temp1));
mask++;
}*/
u=P[u];
}
}
void init(int N1, int M1, std::vector<int> P1, std::vector<int> A) {
n=N1,m=M1;
for(int i=0;i<P1.size();i++) P[i]=P1[i];
for(int i=0;i<P1.size();i++){
E[P[i]].pb(i);
}
for(int i=0;i<m;i++){
dp[n+i][1]=A[i],dp[n+i][0]=1-A[i];
a[i]=A[i];
F[n+i]=1;
}
DFSsetup(0);
DFS(0);
/*for(int i=0;i<=n+m-1;i++){
printf("%i: %i %i\n",i,dp[i][0],dp[i][1]);
}*/
/*for(int i=1;i<=M;i++){
}*/
}
int count_ways(int L, int R) {
if(n==1){
int ct=0;
for(int i=L;i<=R;i++) a[i-1]=1-a[i-1];
for(int i=0;i<=m-1;i++) ct+=a[i];
return ct;
}
for(int i=L;i<=R;i++){
Update(i);
//dp[i][1]=1-dp[i][1];
//dp[i][0]=1-dp[i][0];
}
//DFS(0);
/*for(int i=0;i<=n+m-1;i++){
printf("%i: %i %i\n",i,dp[i][0],dp[i][1]);
}*/
return dp[0][1];
}
