#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll MOD = 1e9+2022;
const ll Nm = 131072; const ll E = 17;
const ll p1 = 2; const ll p2 = 223;
const ll DMAX = 2e6;
ll exp01[DMAX]; ll exp02[DMAX];
//array form: {vp1, vp2, rest}
void gexp() {
exp01[0]=1;
exp02[0]=1;
for (ll i=1;i<DMAX;i++) {
exp01[i]=(exp01[i-1]*p1)%MOD;
exp02[i]=(exp02[i-1]*p2)%MOD;
}
}
ll inv(ll x) {
//cout << "inverse of x="<<x<<" is ";
array<ll,3> a = {x,1,0};
array<ll,3> b = {MOD,0,1};
while (a[0]!=0) {
if (a[0]>b[0]) {
swap(a,b);
} else {
ll k = b[0]/a[0];
for (ll i=0;i<3;i++) {
b[i]-=k*a[i];
}
}
}
ll y = b[1];
ll RVAL = (y+2*MOD+MOD*((-y)/MOD))%MOD;
//cout << RVAL<<"\n";
return RVAL;
}
array<ll,3> gform(ll x) {
array<ll,3> a0 = {0,0,0};
while (x%p1==0) {
a0[0]++;
x=x/p1;
}
while (x%p2==0) {
a0[1]++;
x=x/p2;
}
a0[2]=x;
return a0;
}
ll eval(array<ll,3> a1) {
return (((exp01[a1[0]]*exp02[a1[1]])%MOD)*a1[2])%MOD;
}
array<ll,3> d(array<ll,3> a1, array<ll,3> a2) { //a1/a2
return {a1[0]-a2[0],a1[1]-a2[1],(a1[2]*inv(a2[2]))%MOD};
}
array<ll,3> m(array<ll,3> a1, array<ll,3> a2) {
return {a1[0]+a2[0],a1[1]+a2[1],(a1[2]*a2[2])%MOD};
}
inline ll v2(ll x) {
return __builtin_ctz(x);
}
ll tval;
ll N,M;
ll iwt[Nm]; //initial weights
ll stw0[2*Nm]; //sum of total weights segtree
ll sts[2*Nm]; //sum of active segtree
bool lz[2*Nm]; //lazy tag HAS BEEN APPLIED to current vertex
void lft(ll p) {
if (p>=Nm || lz[p]) {
return;
}
sts[p]=sts[2*p]+sts[2*p+1];
}
void pdn(ll p) {
if (p>=Nm || !lz[p]) {
return;
}
sts[2*p]=(stw0[2*p]-sts[2*p]+MOD)%MOD;
lz[2*p]=1-lz[2*p];
sts[2*p+1]=(stw0[2*p+1]-sts[2*p+1]+MOD)%MOD;
lz[2*p+1]=1-lz[2*p+1];
lz[p]=0;
}
ll updP(ll p) {
for (ll e=E;e>=0;e--) {
pdn(p>>e);
}
sts[p]=(stw0[p]-sts[p]+MOD)%MOD;
lz[p]=1-lz[p];
for (ll e=0;e<=E;e++) {
lft(p>>e);
}
return sts[p];
}
ll upd(ll l, ll r) {
if (l>r) {
return 0;
}
ll vl = v2(l); ll vr = v2(r+1);
if (vl<vr) {
return (updP((l>>vl)+(1<<(E-vl)))+upd(l+(1<<vl),r))%MOD;
} else {
return (updP((r>>vr)+(1<<(E-vr)))+upd(l,r-(1<<vr)))%MOD;
}
}
void init(int _N, int _M, vector<int> P, vector<int> A) {
N = _N; M = _M;
gexp();
vector<ll> fdeg(N,0);
array<ll,3> tstr = {0,0,1};
array<ll,3> cstr[N];
for (ll t=1;t<(N+M);t++) {
fdeg[P[t]]++;
}
tstr=gform(fdeg[0]);
cstr[0]=d((array<ll,3>){0,0,1},tstr);
for (ll t=1;t<N;t++) {
array<ll,3> cpt = gform(fdeg[t]);
//cout << "cpt at t="<<t<<" is "<<cpt[0]<<","<<cpt[1]<<","<<cpt[2]<<"\n";
tstr = m(tstr,cpt);
cstr[t]=d(cstr[P[t]],cpt);
//cout << "cstr[P[t]]="<<cstr[P[t]][0]<<","<<cstr[P[t]][1]<<","<<cstr[P[t]][2]<<"\n";
//cout << "cstr at t="<<t<<" is "<<cstr[t][0]<<","<<cstr[t][1]<<","<<cstr[t][2]<<"\n";
}
for (ll t=N;t<(N+M);t++) {
iwt[t-N]=eval(m(cstr[P[t]],tstr));
//cout << "iwt["<<(t-N)<<"]="<<iwt[t-N]<<"\n";
}
tval = eval(tstr);
for (ll i=0;i<Nm;i++) {
stw0[i+Nm]=iwt[i];
sts[i+Nm]=0;
lz[i+Nm]=0;
}
for (ll p=(Nm-1);p>=0;p--) {
stw0[p]=(stw0[2*p]+stw0[2*p+1])%MOD;
sts[p]=0;
lz[p]=0;
}
for (ll i=0;i<M;i++) {
if (A[i]==0) {
upd(i,i);
}
}
}
int count_ways(int L, int R) {
upd(L-N,R-N);
return (tval-sts[1]+MOD)%MOD;
}
