#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll TAILLE_MAX=200*1000+5,MODU=1000*1000*1000+2022,NB_FACT=3;
ll nbSom,nbSource,rep;
pair<ll,ll> prodGlob[NB_FACT];
vector<ll> pere,prem;
vector<ll> etatDeb;
pair<ll,ll> prodSom[TAILLE_MAX][NB_FACT];
ll nbFils[TAILLE_MAX];
ll valMod;
ll val[TAILLE_MAX];
pair<ll,ll> decompo(ll nb,ll p) {
if (nb==0) {
return {1,0};
}
ll nbOccu=0;
while (nb%p==0) {
nbOccu++;
nb/=p;
}
return {nb%p,nbOccu};
}
ll puis(ll nb,ll expo,ll p) {
if (expo==0) {
return 1;
}
ll ans=puis(nb,expo/2,p);
ans*=ans;
ans%=p;
if (expo%2==1) {
ans*=nb;
ans%=p;
}
return ans;
}
ll inverse(ll nb,ll p) {
return puis(nb,p-2,p);
}
void init(int N, int M, vector<int> P, vector<int> A) {
nbSom=N;
nbSource=M;
for (ll i:P) {
pere.push_back(i);
}
prem={2,223,MODU/(2*223)};
for (ll i:A) {
etatDeb.push_back(i);
}
for (ll i:pere) {
if (i>=0) {
nbFils[i]++;
}
}
for (ll j=0;j<NB_FACT;j++) {
prodGlob[j].first=1;
for (ll i=0;i<nbSom;i++) {
prodGlob[j].first*=decompo(nbFils[i],prem[j]).first;
prodGlob[j].first%=prem[j];
prodGlob[j].second+=decompo(nbFils[i],prem[j]).second;
}
}
for (ll j=0;j<NB_FACT;j++) {
prodSom[0][j]=decompo(nbFils[0],prem[j]);
for (ll i=1;i<nbSom+nbSource;i++) {
prodSom[i][j]=prodSom[pere[i]][j];
prodSom[i][j].first*=decompo(nbFils[i],prem[j]).first;
prodSom[i][j].first%=prem[j];
prodSom[i][j].second+=decompo(nbFils[i],prem[j]).second;
}
}
/*for (ll i=0;i<nbSom+nbSource;i++) {
cout<<i<<" : ";
for (ll j=0;j<NB_FACT;j++) {
cout<<prodSom[i][j].first<<" "<<prodSom[i][j].second<<" ";
}
cout<<endl;
}*/
/*for (int j=0;j<NB_FACT;j++) {
cout<<prodGlob[j].first<<" "<<prodGlob[j].second<<endl;
}*/
for (ll i=0;i<nbSource;i++) {
//cout<<i+nbSom<<" : ";
for (ll j=0;j<NB_FACT;j++) {
if (prodSom[i+nbSom][j].second<prodGlob[j].second) {
valMod=0;
}
else {
valMod=prodGlob[j].first*inverse(prodSom[i+nbSom][j].first,prem[j]);
//cout<<prodGlob[j].first<<" "<<prodSom[i+nbSom][j].first<<" "<<valMod<<" "<<prem[j]<<endl;
valMod%=prem[j];
}
//cout<<valMod<<" ";
val[i]+=valMod*(((MODU/prem[j])*inverse((MODU/prem[j]),prem[j]))%MODU);
}
val[i]%=MODU;
//cout<<endl;
}
for (ll i=0;i<nbSource;i++) {
//cout<<i+nbSom<<" : "<<val[i]<<endl;
rep+=etatDeb[i]*val[i]+MODU;
rep%=MODU;
}
}
int count_ways(int L, int R) {
L-=nbSom;
R-=nbSom;
for (ll i=L;i<=R;i++) {
if (etatDeb[i]==0) {
rep+=val[i];
}
else {
rep-=val[i];
rep+=MODU;
}
rep%=MODU;
etatDeb[i]=1-etatDeb[i];
}
return rep;
}
