#include<bits/stdc++.h>
#include "circuit.h"
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,msh[100009],f[100009],K[100009],mod=1000002022LL,pas,DP[100009],DP2[100009],DP3[100009];
vector <long long> v[100009];
void dfs(long long q, long long w){
if(v[q].size()==0){
DP[q]=1;
return;
}
DP[q]=v[q].size();
for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
dfs((*it),q);
DP[q]*=DP[(*it)];DP[q]%=mod;
}
zx=1;
for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
DP2[(*it)]=zx;
zx*=DP[(*it)];zx%=mod;
}
vector <long long>::iterator it=v[q].end();it--;
zx=1;
while(1){
DP2[(*it)]*=zx;DP2[(*it)]%=mod;
zx*=DP[(*it)];zx%=mod;
if(it==v[q].begin()) break;
it--;
}
}
void dfs2(int q, int w){
DP3[q]*=DP2[q];DP3[q]%=mod;
for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
DP3[(*it)]=DP3[q];
dfs2((*it),q);
}
}
void init(int NN, int MM, std::vector<int> PP, std::vector<int> AA) {
a=NN+MM;
for(i=1; i<a; i++){
msh[i+1]=PP[i]+1;
v[msh[i+1]].push_back(i+1);
}
for(i=NN+1; i<=a; i++){
f[i]=AA[i-NN-1];
}
DP2[1]=1;DP3[1]=1;
dfs(1,0);
dfs2(1,0);
for(i=NN+1; i<=a; i++){
K[i]=DP3[i];
}
}
int count_ways(int L, int R) {
L++;R++;pas=0;
for(i=L; i<=R; i++){
if(f[i]==0) f[i]=1; else f[i]=0;
}
for(i=1; i<=a; i++){
if(f[i]==1){
pas+=K[i];
if(pas>=mod) pas-=mod;
}
}
return pas;
}
