#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=1e5+50,mod=1000002022;
inline ll Plus(ll x,ll y){x%=mod;y%=mod;return (x+y)%mod;}
inline ll Puta(ll x,ll y){x%=mod,y%=mod;return (x*y)%mod;}
ll Pow(ll a,ll b){
ll res=1;
for(ll x=a;b;x=Puta(x,x),b>>=1) if(b&1) res=Puta(res,x);
return res;
}
//glupavi mod nije prost
vector<pair<int,int>>faktor[N+50];bool was[N+50];
struct Broj{
set<pair<int,int>>st;
Broj(){}
Broj(int x){
if(x>1) for(auto i:faktor[x]) st.insert(i);
}
void Pomnozi(Broj x){
for(auto [p,num]:x.st){
auto lb=st.lower_bound({p,0});
if(!(lb==st.end()||(*lb).fi!=p)){
num+=(*lb).se;
st.erase(lb);
}
st.insert({p,num});
}
}
void Podeli(Broj x){
for(auto [p,num]:x.st){
auto lb=st.lower_bound({p,0});
if(lb==st.end()||(*lb).fi!=p) continue;
num=(*lb).se-num;
st.erase(lb);
st.insert({p,num});
}
}
ll Vrednost(){
ll res=1;
for(auto [p,num]:st) res=Puta(res,Pow(p,num));
return res;
}
};
vector<int>E[2*N];
int a[N],n,m,par[2*N];
ll b[2*N];
Broj val1[2*N],Val1[2*N];
void DFSsetup(int u){
val1[u]=Broj(E[u].size());
for(auto i:E[u]){
Val1[i]=Val1[u];
Val1[i].Pomnozi(Broj(E[u].size()));
DFSsetup(i);
val1[u].Pomnozi(val1[i]);
}
if(E[u].empty()) val1[u]=Broj();
}
struct SegTree{
int root,nc,lc[2*N],rc[2*N];ll sum[2*N],sum1[2*N];bool lazy[2*N];
void Build(int &c,int ss,int se){
c=++nc;
if(ss==se){sum1[c]=b[ss];return;}
int mid=ss+se>>1;
Build(lc[c],ss,mid),Build(rc[c],mid+1,se);
sum1[c]=Plus(sum1[lc[c]],sum1[rc[c]]);
}
void update(int c){sum[c]=Plus(sum1[c],mod-sum[c]);lazy[c]^=1;}
void push(int c){if(!lazy[c])return;update(lc[c]),update(rc[c]),lazy[c]=0;}
void Update(int c,int ss,int se,int qs,int qe){
if(qs>qe||qe<ss||se<qs) return;
if(qs<=ss&&se<=qe){update(c);return;}
int mid=ss+se>>1;push(c);
Update(lc[c],ss,mid,qs,qe),Update(rc[c],mid+1,se,qs,qe);
sum[c]=Plus(sum[lc[c]],sum[rc[c]]);
}
}ST;
void init(int n1, int m1, std::vector<int> P, std::vector<int> A){
for(int i=2;i<=N;i++){
if(!was[i]){
for(int j=i;j<=N;j+=i){
was[j]=true;
int temp=j,num=0;
while(temp%i==0) temp/=i,num++;
faktor[j].pb({i,num});
}
}
}
n=n1,m=m1;
for(int i=0;i<P.size();i++) par[i]=P[i],E[par[i]].pb(i);
for(int i=0;i<m;i++) a[i]=A[i];
DFSsetup(0);
for(int i=0;i<m;i++){
int u=i+n;Broj x=val1[0];x.Podeli(Val1[u]);
b[i]=x.Vrednost();
}
ST.Build(ST.root,0,m-1);
for(int i=0;i<m;i++) if(a[i]==1) ST.Update(ST.root,0,m-1,i,i);
}
int count_ways(int L, int R){
L-=n,R-=n;
ST.Update(ST.root,0,m-1,L,R);
return ST.sum[1];
}
