#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]={};
bool swp[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 comp(int 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)));
}
}
void dfs(int u)
{
if (u>=n)
{
dp[u][st[u]]=1;
dp[u][1-st[u]]=0;
l[u]=r[u]=u;
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]);
}
comp(u);
}
void upd(int u,int L,int R)
{
if (swp[u])
{
swap(dp[u][0],dp[u][1]);
for (auto j:nei[u])
swp[j]^=1;
swp[u]=0;
}
if (l[u]>R||r[u]<L)
return ;
if (l[u]>=L&&r[u]<=R)
{
swp[u]^=1;
if (swp[u])
{
swap(dp[u][0],dp[u][1]);
for (auto j:nei[u])
swp[j]^=1;
swp[u]=0;
}
return;
}
for (auto j:nei[u])
upd(j,L,R);
comp(u);
}
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];
dfs(0);
}
int count_ways(int L, int R)
{
upd(0,L,R);
return dp[0][1];
}
