#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
const int N = 2e5 + 10 , mod = 1000002022;
int sbt[N] , n , m , zarib[N] , st_tim[N] , fn_tim[N] , tim;
vector <int> p , a , adj[N];
struct SEG1{
int t[N << 2];
void Build(int node = 1 , int nl = 0 , int nr = m)
{
t[node] = 1;
if(nr - nl == 1)
return;
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
Build(lc , nl , mid); Build(rc , mid , nr);
}
void Add(int val , int l , int r , int node = 1 , int nl = 0 , int nr = m)
{
if(r <= nl || nr <= l)
return;
if(l <= nl && nr <= r)
{
t[node] = 1LL * t[node] * val % mod;
return;
}
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
Add(val , l , r , lc , nl , mid); Add(val , l , r , rc , mid , nr);
}
int Get(int id , int node = 1 , int nl = 0 , int nr = m)
{
if(nr - nl == 1)
return t[node];
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
if(id < mid)
return 1LL * t[node] * Get(id , lc , nl , mid) % mod;
else
return 1LL * t[node] * Get(id , rc , mid , nr) % mod;
}
} seg1;
struct SEG{
int sum[2][N << 2];
int lzy_swp[N << 2];
void Build(int node = 1 , int nl = 0 , int nr = m)
{
lzy_swp[node] = 0;
if(nr - nl == 1)
{
sum[0][node] = sum[1][node] = 0;
sum[a[nl]][node] = seg1.Get(st_tim[nl + n]);
return;
}
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
Build(lc , nl , mid); Build(rc , mid , nr);
sum[0][node] = (sum[0][lc] + sum[0][rc]) % mod;
sum[1][node] = (sum[1][lc] + sum[1][rc]) % mod;
}
void Shift(int node , int lc , int rc)
{
if(!lzy_swp[node])
return;
lzy_swp[node] = 0;
swap(sum[0][lc] , sum[1][lc]);
swap(sum[0][rc] , sum[1][rc]);
lzy_swp[lc] ^= 1;
lzy_swp[rc] ^= 1;
}
void Update(int l , int r , int node = 1 , int nl = 0 , int nr = m)
{
if(r <= nl || nr <= l)
return;
if(l <= nl && nr <= r)
{
swap(sum[0][node] , sum[1][node]);
lzy_swp[node] ^= 1;
return;
}
int mid = (nl + nr) >> 1 , lc = node << 1 , rc = lc | 1;
Shift(node , lc , rc);
Update(l , r , lc , nl , mid);
Update(l , r , rc , mid , nr);
sum[0][node] = (sum[0][lc] + sum[0][rc]) % mod;
sum[1][node] = (sum[1][lc] + sum[1][rc]) % mod;
}
} seg;
void Find_sbt(int v)
{
sbt[v] = adj[v].size();
st_tim[v] = tim;
if(sbt[v] == 0)
{
sbt[v] = 1;
tim++;
fn_tim[v] = tim;
return;
}
for(auto u : adj[v])
{
Find_sbt(u);
sbt[v] = 1LL * sbt[v] * sbt[u] % mod;
}
fn_tim[v] = tim;
}
void Dfs(int v)
{
if(v >= n)
return;
for(int ty = 0 ; ty < 2 ; ty++)
{
int prf = 1;
for(auto u : adj[v])
{
seg1.Add(prf , st_tim[u] , fn_tim[u]);
prf = 1LL * prf * sbt[u] % mod;
}
reverse(adj[v].begin() , adj[v].end());
}
for(auto u : adj[v])
Dfs(u);
}
void init(int nn , int mm , vector <int> pp , vector <int> aa)
{
n = nn;
m = mm;
p = pp;
a = aa;
for(int i = 1 ; i < n + m ; i++)
adj[p[i]].push_back(i);
Find_sbt(0);
seg1.Build();
Dfs(0);
seg.Build();
}
int count_ways(int l , int r)
{
l -= n;
r -= n;
r++;
seg.Update(l , r);
return seg.sum[1][1];
}
