#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
const long long dv=1e9+2022;
long long n,m,pr[200069],a[100069],dp[200069],wg[100069];
vector<long long> al[200069];
struct segtree
{
long long l,r,sm[2];
bool iv;
segtree *p[2];
void bd(long long lh,long long rh)
{
l=lh;
r=rh;
iv=0;
if(l==r)
{
sm[a[l]]=wg[l];
sm[!a[l]]=0;
}
else
{
long long ii,md=(l+r)/2;
for(ii=0;ii<2;ii++)
{
p[ii]=new segtree;
p[ii]->bd(!ii?l:md+1,!ii?md:r);
}
for(ii=0;ii<2;ii++)
{
sm[ii]=(p[0]->sm[ii]+p[1]->sm[ii])%dv;
}
}
}
inline void blc()
{
if(iv)
{
long long ii;
for(ii=0;ii<2;ii++)
{
swap(p[ii]->sm[0],p[ii]->sm[1]);
p[ii]->iv^=1;
}
iv=0;
}
}
void ud(long long lh,long long rh)
{
if(l>rh||r<lh);
else if(l>=lh&&r<=rh)
{
swap(sm[0],sm[1]);
iv^=1;
}
else
{
long long ii;
blc();
for(ii=0;ii<2;ii++)
{
p[ii]->ud(lh,rh);
}
for(ii=0;ii<2;ii++)
{
sm[ii]=(p[0]->sm[ii]+p[1]->sm[ii])%dv;
}
}
}
}
sg;
void dfs(long long x)
{
long long i,sz=al[x].size(),l;
dp[x]=max(sz,1ll);
for(i=0;i<sz;i++)
{
l=al[x][i];
dfs(l);
dp[x]=dp[x]*dp[l]%dv;
}
}
void dfs2(long long x,long long cw)
{
if(x<=n)
{
long long i,sz=al[x].size(),l;
vector<long long> mla,mla2;
mla.push_back(1);
for(i=0;i<sz;i++)
{
l=al[x][i];
mla.push_back(mla[i]*dp[l]%dv);
}
mla2.push_back(1);
for(i=sz-1;i>=0;i--)
{
l=al[x][i];
mla2.push_back(mla2[sz-1-i]*dp[l]%dv);
}
for(i=0;i<sz;i++)
{
l=al[x][i];
dfs2(l,cw*mla[i]%dv*mla2[sz-1-i]%dv);
}
}
else
{
wg[x-n]=cw;
}
}
void init(int on,int om,vector<int> prr,vector<int> aa)
{
long long i;
n=on;
m=om;
for(i=1;i<=n+m;i++)
{
pr[i]=prr[i-1]+1;
}
for(i=1;i<=m;i++)
{
a[i]=aa[i-1];
}
for(i=2;i<=n+m;i++)
{
al[pr[i]].push_back(i);
}
dfs(1);
dfs2(1,1);
sg.bd(1,m);
}
int count_ways(int lb,int rb)
{
lb++;
rb++;
lb-=n;
rb-=n;
sg.ud(lb,rb);
return sg.sm[1];
}
