#include <bits/stdc++.h>
#include "circuit.h"
using ll=long long;
using namespace std;
const ll mod = 1e9+2022, N = 1e5+1, M = 1e5+1;
pair<ll,ll> segt[4*N+5];
bool lazy[4*N+5],vu[N+M];
ll prod[2*N];
vector<int> adj[N+M],rev[N+M];
int n=0, m = 0, stop = -1;
bool ok = false;
pair<ll,ll> crt;
vector<int> pre,nouv,order;
void modify(int idx, int l, int r, int L, int R){
if (r < L or l > R) return;
if (l >= L and r <= R){
if (ok){
swap(segt[idx].first,segt[idx].second);
lazy[idx] = !lazy[idx];
}
else{
segt[idx] = crt;
}
return;
}
if (lazy[idx]){
lazy[2*idx] = !lazy[2*idx];
lazy[2*idx+1] = !lazy[2*idx+1];
swap(segt[2*idx].first,segt[2*idx].second);
swap(segt[2*idx+1].first,segt[2*idx+1].second);
lazy[idx] = 0;
}
int mid = (l+r)/2;
modify(2*idx,l,mid,L,R);
modify(2*idx+1,mid+1,r,L,R);
segt[idx].first = (segt[2*idx].first+segt[2*idx+1].first)%mod;
segt[idx].second = (segt[2*idx].second+segt[2*idx+1].second)%mod;
}
void euler_tour(int node){
if (node >= n){
order.emplace_back(node-n);
}
for (int i:rev[node]){
euler_tour(i);
}
}
void dfs(int node){
for (int i:adj[node]){
if (vu[i]){
stop = i;
return;
}
nouv.emplace_back(i);
dfs(i);
}
}
void upd(int node, int val){
node += N;
prod[node] = val;
node >>= 1;
while (node){
prod[node] = (prod[2*node]*prod[2*node+1])%mod;
node >>= 1;
}
}
ll query(int l, int r){
l += N;
r += N;
ll ans = 1;
while (l <= r){
if (l&1){
ans = (ans*prod[l])%mod;
l++;
}
if (r%2 == 0){
ans = (ans*prod[r])%mod;
r--;
}
l >>= 1;
r >>= 1;
}
return ans;
}
void init(int N, int M, vector<int> P, vector<int> A){
m = M;
n = N;
vector<ll> deg(N+M);
for (int i=1; i<N+M; ++i){
deg[P[i]]++;
adj[i].emplace_back(P[i]);
rev[P[i]].emplace_back(i);
}
fill_n(&prod[0],2*N,1);
for (int i=0; i<N; ++i) upd(i,deg[i]);
euler_tour(0);
for (int i:order){
stop = -1;
nouv.clear();
dfs(i+n);
while (!pre.empty() and pre.back() != stop){
upd(pre.back(),deg[pre.back()]);
vu[pre.back()] = false;
pre.pop_back();
}
reverse(nouv.begin(),nouv.end());
for (int k:nouv){
upd(k,1);
vu[k] = true;
pre.emplace_back(k);
}
ll ans = query(0,n-1);
if (A[i]){
crt = {ans,0};
}
else{
crt = {0,ans};
}
modify(1,0,M-1,i,i);
}
ok = true;
}
int count_ways(int L, int R){
L -= n;
R -= n;
modify(1,0,m-1,L,R);
return segt[1].first;
}
