#include "circuit.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
const long long mod=1e9+2022LL;
vector <long long> g[200010];
long long sz[200010],d[200010],ac[200010],n,dif;
long long weight[200010],a[200010],weightps[200010],seg[800040],laz[800040];
bool marked[800040];
void dfs1(int cur){
sz[cur]=g[cur].size();
sz[cur]=max(sz[cur],1LL);
sz[cur]%=mod;
for (int i:g[cur]){
dfs1(i);
sz[cur]=sz[cur]*sz[i]%mod;
}
if (!g[cur].size()){
return;
} else {
long long fr[g[cur].size()],ba[g[cur].size()];
for (int i=0; i<g[cur].size(); i++){
if (!i) fr[i]=sz[g[cur][i]]%mod;
else fr[i]=fr[i-1]*sz[g[cur][i]]%mod;
}
for (int i=g[cur].size()-1; i>=0; i--){
if (i==g[cur].size()-1) ba[i]=sz[g[cur][i]]%mod;
else ba[i]=ba[i+1]*sz[g[cur][i]]%mod;
}
for (int i=0; i<g[cur].size(); i++){
int t=1;
if (i) t=t*fr[i-1]%mod;
if (i+1<g[cur].size()) t=t*ba[i+1]%mod;
d[g[cur][i]]=t%mod;
}
}
}
void dfs2(int cur){
for (int i:g[cur]){
ac[i]=ac[cur]%mod*d[i]%mod;
dfs2(i);
}
}
void build(int id,int tl,int tr){
if (tl==tr){
seg[id]=a[tl]*weight[tl]%mod;
return;
}
int tm=(tl+tr)/2;
build(2*id,tl,tm);
build(2*id+1,tm+1,tr);
seg[id]=(seg[2*id]+seg[2*id+1])%mod;
}
void pushdown(int id,int tl,int tr){
if (!marked[id]) return;
int tm=(tl+tr)/2;
if (laz[id]%2==1){
seg[2*id]=(weightps[tm]-weightps[tl-1]+mod-seg[2*id]+mod)%mod;
seg[2*id+1]=(weightps[tr]-weightps[tm]+mod-seg[2*id+1]+mod)%mod;
}
marked[2*id]=1; laz[2*id]+=laz[id];
marked[2*id+1]=1; laz[2*id+1]+=laz[id];
marked[id]=0; laz[id]=0;
}
void update(int id,int tl,int tr,int l,int r){
if (l>r) return;
if (l<=tl&&tr<=r){
seg[id]=(weightps[tr]-weightps[tl-1]+mod-seg[id]+mod)%mod;
laz[id]++;
marked[id]=1;
return;
}
pushdown(id,tl,tr);
int tm=(tl+tr)/2;
update(2*id,tl,tm,l,min(r,tm));
update(2*id+1,tm+1,tr,max(tm+1,l),r);
seg[id]=(seg[2*id]+seg[2*id+1])%mod;
}
long long query(int id,int tl,int tr,int l,int r){
if (l>r) return 0;
if (l<=tl&&tr<=r) return seg[id];
pushdown(id,tl,tr);
int tm=(tl+tr)/2;
long long lx=query(2*id,tl,tm,l,min(r,tm));
long long rx=query(2*id+1,tm+1,tr,max(l,tm+1),r);
return (lx+rx)%mod;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n=M; dif=N-1;
for (int i=1; i<N+M; i++) g[P[i]].push_back(i);
dfs1(0);
ac[0]=1;
dfs2(0);
for (int i=1; i<=n; i++) weight[i]=ac[i+N-1]%mod;
for (int i=1; i<=n; i++) weightps[i]=(weightps[i-1]+weight[i])%mod;
for (int i=1; i<=n; i++) a[i]=A[i-1];
build(1,1,n);
}
int count_ways(int L, int R) {
L-=dif; R-=dif;
update(1,1,n,L,R);
return query(1,1,n,1,n)%mod;
}
