#include "circuit.h"
#include <bits/stdc++.h>
#define int long long
const int mod = 1e9+2022;
using namespace std;
vector<int> prsum;
int summ(int l,int r)
{
return prsum[r]-(l>0?prsum[l-1]:0);
}
struct seggy{
int n;
vector<int> lazy,tree;
void build(int l,int r,int idx,vector<int>&v)
{
if(l==r)
{
tree[idx] = v[l];
return;
}
int mid = l+r>>1;
build(l,mid,2*idx,v);
build(mid+1,r,2*idx+1,v);
tree[idx] = tree[2*idx]+tree[2*idx+1];
}
seggy(vector<int>&v){
n = v.size();
lazy.resize(4*n,0),tree.resize(4*n,0);
build(0,n-1,1,v);
}
void pass(int l,int r,int idx)
{
if(lazy[idx]==0)
return;
tree[idx] = summ(l,r)-tree[idx];
lazy[idx] = 0;
if(l==r)return;
lazy[2*idx]^=1;
lazy[2*idx+1]^=1;
}
int query(int l,int r,int L,int R,int idx)
{
pass(l,r,idx);
if(l>R||r<L)return 0ll;
if(l>=L&&r<=R)return tree[idx];
int mid = l+r>>1;
return query(l,mid,L,R,2*idx)+query(mid+1,r,L,R,2*idx+1);
}
int query(int l,int r)
{
return query(0,n-1,l,r,1);
}
void update(int l,int r,int L,int R,int idx)
{
pass(l,r,idx);
if(l>R||r<L)return;
if(l>=L&&r<=R)
{
lazy[idx]=1;
pass(l,r,idx);
return;
}
int mid = l+r>>1;
update(l,mid,L,R,2*idx);
update(mid+1,r,L,R,2*idx+1);
tree[idx] = tree[2*idx]+tree[2*idx+1];
}
void update(int l,int r)
{
update(0,n-1,l,r,1);
}
};
vector<int> dumy = {0,1};
seggy mile(dumy);
int n,m;
vector<int> p,v;
vector<int> coeff;
void init(signed N, signed M, std::vector<signed> P, std::vector<signed> A) {
n = N,m = M;
p.resize(n+m),v.resize(m);
vector<int> mult(n+m,1);
coeff.resize(m);
vector<vector<int>> graph(n+m);
for(int i = 0; i < n+m; i++)
p[i] = P[i];
for(int i = 0; i < m; i++)
v[i] = A[i];
for(int i = 1; i < n+m; i++)
graph[p[i]].push_back(i);
vector<int> hlp(n+m,1);
function<void(int)> dfs = [&](int cur)
{
if(graph[cur].empty())return;
for(int a: graph[cur])
dfs(a);
int k = graph[cur].size();
vector<int> suf(k,1);
vector<int> pref(k,1);
for(int i = 0; i < k; i++)
pref[i] = (i>0?pref[i-1]:1)*mult[graph[cur][i]]%mod;
for(int i = k-1; i >= 0; i--)
suf[i] = (i<k-1?suf[i+1]:1)*mult[graph[cur][i]]%mod;
for(int i = 0; i <k;i++)
hlp[graph[cur][i]]=(i>0?pref[i-1]:1)*(i<k-1?suf[i+1]:1)%mod;
for(int a :graph[cur])
mult[cur]=mult[a]*mult[cur]%mod;
mult[cur]=k*mult[cur]%mod;
};
dfs(0);
function<void(int,int)> pass = [&](int cur,int run){
if(cur>=n)
coeff[cur-n] = run*hlp[cur]%mod;
else
{
for(int a: graph[cur])
pass(a,run*hlp[cur]%mod);
}
};
pass(0,1);
prsum.resize(m);
for(int i = 0; i < m; i++)
prsum[i] = (i>0?prsum[i-1]:0)+coeff[i];
mile = seggy(coeff);
for(int i = 0; i< m; i++)
if(!v[i])
mile.update(i,i);
}
signed count_ways(signed L, signed R) {
mile.update(L-n,R-n);
return mile.tree[1]%mod;
}
