#include "circuit.h"
#include <vector>
#include <iostream>
using namespace std;
#define ll long long
int const NPM=2e5+10,mod=1000002022;
vector<int>nei[NPM]={};
long long dp[NPM][2]={};
long long ways[2][NPM]={};
int P[NPM]={};
int l[NPM],r[NPM];
bool st[NPM]={};
int n,m;
long long mul(ll a,ll b)
{
return (a*b)%mod;
}
long long add(ll a,ll b)
{
return (a+b)%mod;
}
void dfs(int u)
{
if (u>=n)
{
dp[u][st[u]]=1;
dp[u][1-st[u]]=0;
l[u]=r[u]=u;
// cout<<u<<' '<<dp[u][0]<<' '<<dp[u][1]<<endl;
return;
}
l[u]=NPM,r[u]=0;
for (auto i:nei[u])
{
dfs(i);
l[u]=min(l[i],l[u]);
r[u]=max(r[i],r[u]);
}
int sz=nei[u].size();
for (int i=1;i<=sz;i++)
ways[0][i]=0;
ways[0][0]=1;
for (auto i:nei[u])
{
for (auto j:{0,1})
{
for (int k=sz;k>=j;k--)
ways[1][k]=add(ways[1][k],mul(ways[0][k-j],dp[i][j]));
}
for (int k=0;k<=sz;k++)
{
ways[0][k]=ways[1][k];
ways[1][k]=0;
}
}
dp[u][1]=0;
dp[u][0]=0;
for (int i=0;i<=sz;i++)
{
dp[u][1]=add(dp[u][1],mul(ways[0][i],i));
dp[u][0]=add(dp[u][0],mul(ways[0][i],(sz-i)));
}
// cout<<u<<' '<<dp[u][0]<<' '<<dp[u][1]<<endl;
}
void init(int N, int M, vector<int> P, vector<int> A)
{
n=N;
m=M;
for (int i=1;i<n+m;i++)
nei[P[i]].push_back(i);
for (int i=n;i<n+m;i++)
st[i]=A[i-n];
}
int count_ways(int L, int R)
{
for (int i=L;i<=R;i++)
st[i]^=1;
dfs(0);
return dp[0][1];
}
