#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000002022LL;
const int N = 1<<18;
ll drz[2 * N][2];
int laz[2 * N];
vector<int> ed[N];
ll il[N];
int bas;
void Query(int v, int p, int k, int pz, int kz)
{
if(p > kz || k < pz) return;
if(p >= pz && k <= kz)
{
swap(drz[v][0], drz[v][1]);
laz[v] ^= 1;
return;
}
Query(v * 2, p, (p + k) / 2, pz, kz);
Query(v * 2 + 1, (p + k) / 2 + 1, k, pz, kz);
drz[v][0] = (drz[v * 2][0] + drz[v * 2 + 1][0]) % M;
drz[v][1] = (drz[v * 2][1] + drz[v * 2 + 1][1]) % M;
if(laz[v] == 1)
swap(drz[v][0], drz[v][1]);
}
ll QP(ll a, ll n)
{
ll ans = 1LL;
while(n > 0LL)
{
if(n % 2LL == 1LL)
ans = (ans * a) % M;
a = (a * a) % M;
n /= 2LL;
}
return ans;
}
void DFSL(int v)
{
il[v] = max(1LL, (ll)ed[v].size());
for(int i = 0; i < (int)ed[v].size(); ++i)
{
DFSL(ed[v][i]);
il[v] = (il[v] * il[ed[v][i]]) % M;
}
}
void DFS(int v, ll cur)
{
if(v > bas)
{
drz[v - bas + N][0] += cur;
return;
}
vector<ll> prf;
for(int i = 0; i < (int)ed[v].size(); ++i)
{
prf.pb(il[ed[v][i]]);
if(i > 0)
prf[i] = (prf[i] * prf[i - 1]) % M;
}
for(int i = (int)ed[v].size() - 1; i >= 0; --i)
{
ll xd = cur;
if(i > 0) xd = (xd * prf[i - 1]) % M;
DFS(ed[v][i], xd);
cur = (cur * il[ed[v][i]]) % M;
}
}
void init(int XN, int XM, vector<int> P, vector<int> A)
{
int n = XN + XM;
bas = XN;
for(int i = 1; i < n; ++i)
ed[P[i] + 1].pb(i + 1);
DFSL(1);
DFS(1, 1LL);
for(int i = 1; i <= n - bas; ++i)
{
if(A[i - 1] == 0)
swap(drz[i + N][0], drz[i + N][1]);
}
for(int i = N - 1; i >= 1; --i)
{
drz[i][0] = (drz[i * 2][0] + drz[i * 2 + 1][0]) % M;
drz[i][1] = (drz[i * 2][1] + drz[i * 2 + 1][1]) % M;
}
}
int count_ways(int L, int R)
{
++L; ++R;
L -= bas; R -= bas;
Query(1, 0, N - 1, L, R);
return drz[1][0];
}
