#include "circuit.h"
#include <bits/stdc++.h>
#define ll long long
#define sz(s) (int)s.size()
#define pb push_back
using namespace std;
const int MAX=2e5+10;
const int mod=1000002022;
int n,m;
vector<int> a;
vector<int> g[MAX];
int dp[MAX],s[MAX];
void dfs(int v){
if(g[v].empty()){
dp[v]=a[v-n];
s[v]=1;
return;
}
s[v]=sz(g[v]);
for(auto to:g[v]){
dfs(to);
s[v]=s[v]*1ll*s[to]%mod;
}
vector<int> d(n+m,0);
d[0]=1;
for(int i=0;i<sz(g[v]);i++){
int to=g[v][i];
for(int j=i+1;j>=0;j--){
int p=d[j];
d[j]=d[j]*1ll*(s[to]-dp[to]+mod)%mod;
if(j-1>=0)d[j]+=d[j-1]*1ll*dp[to]%mod;
d[j]%=mod;
}
}
for(int i=1;i<=sz(g[v]);i++){
dp[v]+=i*1ll*d[i]%mod;
dp[v]%=mod;
}
}
struct segtree{
int t[4*MAX];
int s[4*MAX];
int add[4*MAX];
void build(int v,int tl,int tr,vector<int> &a){
add[v]=0;
if(tl==tr){
s[v]=1;
t[v]=a[tl];
return;
}
int tm=(tl+tr)/2;
build(2*v,tl,tm,a);
build(2*v+1,tm+1,tr,a);
t[v]=0;
for(int i=1;i<4;i++){
int prod=1;
if(i&1){
prod=prod*1ll*t[2*v]%mod;
}
else{
prod=prod*1ll*(s[2*v]-t[2*v]+mod)%mod;
}
if(i&2){
prod=prod*1ll*t[2*v+1]%mod;
}
else{
prod=prod*1ll*(s[2*v+1]-t[2*v+1]+mod)%mod;
}
t[v]=t[v]+__builtin_popcount(i)*1ll*prod%mod;
t[v]%=mod;
}
// cout<<v<<" "<<tl<<" "<<tr<<" "<<t[v]<<"\n";
s[v]=2ll*s[2*v]*s[2*v+1]%mod;
}
void make(int v){
add[v]^=1;
t[v]=(s[v]-t[v]+mod)%mod;
}
void push(int v){
if(add[v]){
make(2*v);
make(2*v+1);
}
add[v]=0;
}
void update(int v,int tl,int tr,int l,int r){
if(l>r||tl>r||l>tr)return;
if(l<=tl&&tr<=r){
make(v);
// cout<<l<<" "<<r<<" "<<tl<<" "<<tr<<" "<<t[v] <<"\n";
return;
}
int tm=(tl+tr)/2;
push(v);
update(2*v,tl,tm,l,r);
update(2*v+1,tm+1,tr,l,r);
t[v]=0;
for(int i=1;i<4;i++){
int prod=1;
if(i&1){
prod=prod*1ll*t[2*v]%mod;
}
else{
prod=prod*1ll*(s[2*v]-t[2*v]+mod)%mod;
}
if(i&2){
prod=prod*1ll*t[2*v+1]%mod;
}
else{
prod=prod*1ll*(s[2*v+1]-t[2*v+1]+mod)%mod;
}
t[v]=t[v]+__builtin_popcount(i)*1ll*prod%mod;
t[v]%=mod;
}
}
}T;
bool st=0;
void init(int N, int M,vector<int> P,vector<int> A) {
n=N;
m=M;
a=A;
for(int i=1;i<N+M;i++){
g[P[i]].pb(i);
}
{
int x=1;
while(x<M)x*=2;
if(x==M&&N==M-1)st=1;
}
if(st)T.build(1,0,M-1,a);
}
int count_ways(int L, int R) {
// cout<<st<<"\n";
if(st){
T.update(1,0,m-1,L-n,R-n);
return T.t[1];
}
for(int i=0;i<n+m;i++)dp[i]=0;
for(int i=L;i<=R;i++)a[i-n]^=1;
dfs(0);
return dp[0];
}
