#define ll long long
#define pll pair<ll, ll>
#define MOD 1000002022
#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
bool subFirst = false;
ll n = 0;
vector<ll> a(0);
vector<vector<ll>> adjlist(0);
void init(int N, int M, std::vector<int> P, std::vector<int> A)
{
n = N+M;
subFirst = (N <= 1000 && M <= 1000);
if(subFirst)
{
adjlist.assign(n, vector<ll> (0));
for(ll i = 1; i < n; i++)
{
adjlist[P[i]].push_back(i);
}
a.assign(n, 0);
for(ll i = N; i < n; i++)
{
a[i] = A[i-N];
}
}
}
pll dfs(int i) //On, off
{
if(adjlist[i].empty())
{
return {a[i], 1-a[i]};
}
ll c = adjlist[i].size();
ll all = c;
vector<ll> dp(c+1, 0); //Possibilities for being on
dp[0] = 1;
for(ll j : adjlist[i])
{
pll p = dfs(j);
all = (all * ((p.first+p.second)%MOD))%MOD;
vector<ll> postdp(c+1, 0);
for(ll k = 0; k <= c; k++)
{
postdp[k] = (dp[k]*p.second)%MOD;
if(k > 0)
{
postdp[k] = (postdp[k] + (dp[k-1]*p.first)%MOD)%MOD;
}
}
dp = postdp;
}
ll on = 0;
for(ll k = c; k > 0; k--)
{
on = (on+((dp[k]*k)%MOD))%MOD;
}
return {on, (all+MOD-on)%MOD};
}
int count_ways(int L, int R)
{
if(subFirst)
{
for(ll i = L; i <= R; i++)
{
a[i] = 1-a[i];
}
return dfs(0).first;
}
return -1;
}
