#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
struct noeud{
ll give0,give1,coeff,deb,fin;
};
const ll TAILLE_MAX=300*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];
noeud cumu[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 prepa(ll pos,ll debInter,ll finInter) {
cumu[pos].deb=debInter;
cumu[pos].fin=finInter;
if (debInter==finInter) {
cumu[pos].give0=val[debInter]%MODU;
}
else {
ll midInter=(debInter+finInter)/2;
prepa(2*pos,debInter,midInter);
prepa(2*pos+1,midInter+1,finInter);
cumu[pos].give0=(cumu[2*pos].give0+cumu[2*pos+1].give0)%MODU;
}
}
void pushFlag(ll pos) {
if (cumu[pos].coeff%2==1) {
swap(cumu[pos].give0,cumu[pos].give1);
}
if (cumu[pos].deb!=cumu[pos].fin) {
cumu[2*pos].coeff+=cumu[pos].coeff;
cumu[2*pos].coeff%=2;
cumu[2*pos+1].coeff+=cumu[pos].coeff;
cumu[2*pos+1].coeff%=2;
}
cumu[pos].coeff=0;
}
pair<ll,ll> update(ll pos,ll debInter,ll finInter) {
//cout<<pos<<" "<<debInter<<" "<<finInter<<" : ";
if (cumu[pos].deb>finInter or cumu[pos].fin<debInter) {
//cout<<"A"<<endl;
pushFlag(pos);
return {cumu[pos].give0,cumu[pos].give1};
}
if (cumu[pos].deb>=debInter and cumu[pos].fin<=finInter) {
//cout<<"B"<<endl;
cumu[pos].coeff++;
pushFlag(pos);
return {cumu[pos].give0,cumu[pos].give1};
}
//cout<<"C"<<endl;
pushFlag(pos);
auto gauche=update(2*pos,debInter,finInter);
auto droite=update(2*pos+1,debInter,finInter);
cumu[pos].give0=(gauche.first+droite.first)%MODU;
cumu[pos].give1=(gauche.second+droite.second)%MODU;
return {cumu[pos].give0,cumu[pos].give1};
}
void afficher() {
cout<<endl;
for (ll i=1;i<20;i++) {
cout<<i<<" : "<<cumu[i].deb<<" "<<cumu[i].fin<<" "<<cumu[i].coeff<<" "<<cumu[i].give0<<" "<<cumu[i].give1<<endl;
}
cout<<endl;
}
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;
}
prepa(1,0,nbSource-1);
//afficher();
for (ll i=0;i<nbSource;i++) {
//cout<<i+nbSom<<" : "<<val[i]<<endl;
if (etatDeb[i]==1) {
rep=update(1,i,i).second;
//afficher();
}
}
}
int count_ways(int L, int R) {
L-=nbSom;
R-=nbSom;
rep=update(1,L,R).second;
return rep%MODU;
}
