#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 1e9 + 2022;
const int TOT = 497758632;
const int MAXN = 121010;
// https://codeforces.com/blog/entry/18051
bool lazy[MAXN]; int val[MAXN<<1], sum[MAXN<<1];
int h = sizeof(int) * 8 - __builtin_clz(MAXN);
void app(int x) {
val[x] = sum[x] - val[x];
if(val[x]<0) val[x]+=MOD;
if(x<MAXN) lazy[x]^=1;
}
void build(int x) {
while(x>>=1) {
int erm = val[x<<1]+val[x<<1|1];
if(erm>=MOD) erm-=MOD;
val[x]=(lazy[x]?(sum[x]<erm?sum[x]-erm+MOD:sum[x]-erm):erm);
}
}
void push(int x) {
for(int s=h;s;--s) {
int i = x>>s;
if(lazy[i]) app(i<<1),app(i<<1|1);
lazy[i]=0;
}
}
void up(int l, int r) {
l += MAXN, r += MAXN;
int l0 = l, r0 = r;
for(;l<r;l>>=1,r>>=1) {
if(l&1) app(l++);
if(r&1) app(--r);
}
build(l0); build(r0-1);
}
int qry(int l, int r) {
l += MAXN, r+=MAXN;
push(l); push(r-1);
int ans = 0;
for(;l<r;l>>=1,r>>=1) {
if(l&1) {ans+=val[l++]; if(ans>=MOD) ans-=MOD;}
if(r&1) {ans+=val[--r]; if(ans>=MOD) ans-=MOD;}
}
return ans;
}
int exp(int a, int b) {
if(!b) return 1;
return (1LL*exp((1LL*a*a)%MOD,b>>1)*(b&1?a:1))%MOD;
}
int n, m;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N;
m = M;
int deg[N+M], deg2[N+M], deg223[N+M], weight[N+M], weight2[N+M], weight223[N+M];
fill(deg,deg+N+M,0);
fill(deg2,deg2+N+M,0);
fill(deg223,deg223+N+M,0);
for(int i=1;i<N+M;i++) deg[P[i]]++;
for(int i=0;i<N;i++) {
while(!(deg[i]%2)) deg[i]/=2, deg2[i]++;
while(!(deg[i]%223)) deg[i]/=223, deg223[i]++;
}
int ways = 1, ways2 = 0, ways223 = 0;
for(int i=0;i<N;i++) ways = (1LL * ways * deg[i]) % MOD, ways2+=deg2[i], ways223+=deg223[i];
weight[0]=1; weight2[0] = weight223[0] = 0;
for(int i=1;i<N+M;i++) weight[i] = (1LL*weight[P[i]] * exp(deg[P[i]], TOT - 1))%MOD, weight2[i] = weight2[P[i]] - deg2[P[i]], weight223[i] = weight223[P[i]] - deg223[P[i]];
for(int i=0;i<M;i++) {
sum[i+MAXN] = (1LL * weight[i+N] * ways) % MOD;
sum[i+MAXN] = (1LL * sum[i+MAXN] * exp(2,ways2 + weight2[i+N])) % MOD;
sum[i+MAXN] = (1LL * sum[i+MAXN] * exp(223,ways223 + weight223[i+N])) % MOD;
val[i+MAXN] = sum[i+MAXN]*A[i];
}
for(int i=MAXN;--i;) {
sum[i]=sum[i<<1]+sum[i<<1|1];
if(sum[i]>=MOD) sum[i]-=MOD;
val[i]=val[i<<1]+val[i<<1|1];
if(val[i]>=MOD) val[i]-=MOD;
}
}
int count_ways(int L, int R) {
up(L-n,R-n+1);
return qry(0,m);
}
/*
main() {
int x = 1e9 + 2022; ll totient = 1e9 + 2022;
for(int i=2;x>1;i++) if(!(x%i)) {
while(!(x%i)) x /= i;
totient *= (i-1); totient /= i;
cout << i << " ";
}
cout << totient;
}
*/
