#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 3e5;
const ll MOD = 1e9+2022;
int N, M;
vector<int> adj[MAXN+10];
ll phi[MAXN+10];
vector<ll> PV[MAXN+10], SV[MAXN+10];
int S[MAXN+10];
ll A[MAXN+10];
void dfs(int now)
{
if(adj[now].empty())
{
phi[now]=1;
return;
}
phi[now]=adj[now].size();
for(auto nxt : adj[now])
{
dfs(nxt);
PV[now].push_back(phi[nxt]);
SV[now].push_back(phi[nxt]);
phi[now]=phi[now]*phi[nxt]%MOD;
}
for(int i=1; i<PV[now].size(); i++) PV[now][i]=PV[now][i-1]*PV[now][i]%MOD;
for(int i=SV[now].size()-2; i>=0; i--) SV[now][i]=SV[now][i+1]*SV[now][i]%MOD;
}
void dfs2(int now, ll val)
{
if(adj[now].empty())
{
A[now]=val;
return;
}
for(int i=0; i<adj[now].size(); i++)
{
int nxt=adj[now][i];
ll t=1;
if(i-1>=0) t=t*PV[now][i-1]%MOD;
if(i+1<SV[now].size()) t=t*SV[now][i+1]%MOD;
dfs2(nxt, val*t%MOD);
}
}
pll operator + (const pll &p, const pll &q)
{
return {(p.first+q.first)%MOD, (p.second+q.second)%MOD};
}
struct SEG
{
pll tree[MAXN*4+10];
int lazy[MAXN*4+10];
void init(int node, int tl, int tr)
{
lazy[node]=0;
if(tl==tr)
{
tree[node]=pll(0, A[tl]);
if(S[tl]) swap(tree[node].first, tree[node].second);
return;
}
int mid=tl+tr>>1;
init(node*2, tl, mid);
init(node*2+1, mid+1, tr);
tree[node]=tree[node*2]+tree[node*2+1];
}
void busy(int node, int tl, int tr)
{
if(lazy[node]) swap(tree[node].first, tree[node].second);
if(tl!=tr) lazy[node*2]^=lazy[node], lazy[node*2+1]^=lazy[node];
lazy[node]=0;
}
void update(int node, int tl, int tr, int l, int r)
{
busy(node, tl, tr);
if(l<=tl && tr<=r)
{
lazy[node]=1;
busy(node, tl, tr);
return;
}
if(r<tl || tr<l) return;
int mid=tl+tr>>1;
update(node*2, tl, mid, l, r);
update(node*2+1, mid+1, tr, l, r);
tree[node]=tree[node*2]+tree[node*2+1];
}
ll query()
{
if(!lazy[1]) return tree[1].first;
else return tree[1].second;
}
}seg;
void init(int _N, int _M, vector<int> _P, vector<int> _Q)
{
N=_N; M=_M;
for(int i=1; i<N+M; i++) adj[_P[i]].push_back(i);
for(int i=N; i<N+M; i++) S[i]=_Q[i-N];
dfs(0);
dfs2(0, 1);
seg.init(1, N, N+M-1);
}
int count_ways(int L, int R)
{
seg.update(1, N, N+M-1, L, R);
return seg.query();
}
