#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod=1000002022;
int n,m;
vector<int> v[200001];
long long c[200001],c1[200001],c2[200001];
long long dp[200001][2];
int a[200001];
void dfs(int i)
{
//cout<<i<<" in"<<endl;
c[i]=v[i].size();
if(c[i]==0)
{
c[i]=1;
dp[i][a[i]]=1;
dp[i][a[i]^1]=0;
return;
}
dp[i][0]=dp[i][1]=0;
for(int j=0;j<v[i].size();j++)
{
int nb=v[i][j];
dfs(nb);
c[i]*=c[nb];
c[i]%=mod;
c1[nb]=c[nb];
if(j!=0)c1[nb]*=c1[v[i][j-1]];
c1[nb]%=mod;
}
for(int j=v[i].size()-1;j>=0;j--)
{
int nb=v[i][j];
c2[nb]=c[nb];
if(j!=v[i].size()-1)c2[nb]*=c2[v[i][j+1]];
c2[nb]%=mod;
}
for(int j=0;j<v[i].size();j++)
{
int nb=v[i][j];
int wo=1;
if(j!=0)wo*=c1[v[i][j-1]];
wo%=mod;
if(j!=v[i].size()-1)wo*=c2[v[i][j+1]];
wo%=mod;
dp[i][0]+=dp[nb][0]*wo;
dp[i][0]%=mod;
dp[i][1]+=dp[nb][1]*wo;
dp[i][1]%=mod;
}
//cout<<i<<" out"<<endl;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
n=N;
m=M;
for(int i=1;i<P.size();i++)
v[P[i]].push_back(i);
for(int i=0;i<A.size();i++)
a[n+i]=A[i];
return;
}
int count_ways(int L, int R)
{
for(int i=L;i<=R;i++)
a[i]^=1;
dfs(0);
return dp[0][1];
}
