#include<bits/stdc++.h>
#include "circuit.h"
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,mod=1000002022LL,dp[200009],ALL[200009],f[200009],L,R,pr[200009],sf[200009],pas,N,seg[800009],seg2[800009],JM[200009],M,l,r,z,za;
vector <long long> v[200009];
void pushdown(long long q, long long w, long long rr){
if(q!=w){
seg2[rr*2]^=seg2[rr];
seg2[rr*2+1]^=seg2[rr];
}
if(seg2[rr]!=0){
seg2[rr]=0;
seg[rr]=JM[w]-JM[q-1]-seg[rr]+mod*2;
seg[rr]%=mod;
}
}
void upd(long long q, long long w, long long rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
seg2[rr]^=1;
pushdown(q,w,rr);
return;
}
upd(q,(q+w)/2,rr*2);
upd((q+w)/2+1,w,rr*2+1);
seg[rr]=seg[rr*2]+seg[rr*2+1];
seg[rr]%=mod;
}
void read(long long q, long long w, long long rr){
pushdown(q,w,rr);
if(q>r||w<l) return;
if(q>=l&&w<=r){
z+=seg[rr];
z%=mod;
return;
}
read(q,(q+w)/2,rr*2);
read((q+w)/2+1,w,rr*2+1);
}
void dfs(int q, int w){
if(v[q].size()==0){
ALL[q]=1;
return;
}
ALL[q]=v[q].size();
for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
dfs((*it),q);
ALL[q]*=ALL[(*it)];ALL[q]%=mod;
}
long long qw=1;
for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
pr[(*it)]=qw;
qw*=ALL[(*it)];qw%=mod;
}
vector <long long>::iterator it=v[q].end();it--;
qw=1;
for( ; ; ){
sf[(*it)]=qw;
qw*=ALL[(*it)];qw%=mod;
if(it==v[q].begin()) break;
it--;
}
}
void dfs2(int q, int w){
dp[q]=dp[w];
dp[q]*=pr[q];dp[q]%=mod;
dp[q]*=sf[q];dp[q]%=mod;
for(vector <long long>::iterator it=v[q].begin(); it!=v[q].end(); it++){
dfs2((*it),q);
}
}
void init(int NN, int MM, std::vector<int> P, std::vector<int> A) {
a=NN+MM;N=NN;M=MM;
for(ii=1; ii<P.size(); ii++){
i=ii+1;
v[P[ii]+1].push_back(i);
}
for(i=N+1; i<=a; i++){
f[i]=A[i-N-1];
}
dfs(1,0);
pr[1]=sf[1]=1;
dp[0]=1;
dfs2(1,0);
za=1;
while(za<a-N) za*=2;
for(i=N+1; i<=a; i++){
JM[i-N]=dp[i];
}
for(i=1; i<=M; i++){
JM[i]+=JM[i-1];JM[i]%=mod;
}
for(i=N+1; i<=a; i++){
if(f[i]==0) continue;
l=i-N;r=i-N;z=1;
upd(1,za,1);
}
/*for(i=1; i<=a; i++){
cout<<dp[i]<<" "<<pr[i]<<" "<<sf[i]<<"\n";
}*/
}
int count_ways(int LL, int RR) {
L=LL+1;R=RR+1;
/*for(i=L; i<=R; i++) f[i]^=1;
pas=0;
for(i=N+1; i<=a; i++){
if(f[i]==1){
pas+=dp[i];pas%=mod;
}
}*/
l=L-N;r=R-N;z=1;
upd(1,za,1);
l=1;r=a-N;z=0;
read(1,za,1);
pas=z;
return pas;
}
