#include "circuit.h"
#ifdef LOCAL
#include "stub.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define iint signed
#define REP(i,n) for(int i=0;i<(n);i++)
#define REP1(i,n) for(int i=1;i<=(n);i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define RREP1(i,n) for(int i=(n);i>=1;i--)
#define f first
#define s second
#define pb push_back
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((int)((x).size()))
#define pii pair<int,int>
#define Graph vector<vector<int>>
#define Graphw vector<vector<pii>>
template<typename S> void chmin(S &x,S y) { x=min(x,y); }
template<typename S> void chmax(S &x,S y) { x=max(x,y); }
#define Vi vector<int>
#define Vpii vector<pii>
#ifdef LOCAL
#define op(x) cout<<(#x)<<"="<<(x)<<", ";
#define ope(x) cout<<(#x)<<"="<<(x)<<endl;
#define oparr(x) {cout<<(#x)<<":";for(auto allen:(x)) cout<<allen<<" ";cout<<" size="<<(x).size()<<endl;}
#define entr cout<<endl;
#else
#define op(x) ;
#define ope(x) ;
#define oparr(x) ;
#define entr ;
#endif
template<typename S>
ostream& operator<<(ostream& os,vector<S> p) { for(auto allen:p) os<<allen<<' ';return os<<'\n'; }
template<typename S>
istream& operator>>(istream& os,vector<S> &p) { for(auto &allen:p) os>>allen;return os; }
const int mod=(int)1e9+2022;
struct SEG {
struct Seg {
int sum,val,t;
};
void addtag(Seg &s,int t) {
if(t) {
s.val=(s.sum-s.val)%mod;
s.t^=1;
}
}
void push(Seg &a,Seg &b,Seg &c) {
addtag(b,a.t);
addtag(c,a.t);
a.t=0;
}
void pull(Seg &a,Seg &b,Seg &c) {
a.sum=b.sum+c.sum;
a.val=b.val+c.val;
}
int n;
vector<Seg> s;
void build(int w,int l,int r,Vi &a,Vi &v) {
s[w].t=0;
if(l==r) {
s[w]={v[l],v[l]*a[l]};
return;
}
int m=l+r>>1;
build(w<<1,l,m,a,v);
build(w<<1|1,m+1,r,a,v);
pull(s[w],s[w<<1],s[w<<1|1]);
op(l)op(r)op(s[w].sum)ope(s[w].val)
}
void init(int _n,Vi _a,Vi _w) {
n=_n;
oparr(_a)oparr(_w)
s=vector<Seg>(n<<2);
build(1,0,n-1,_a,_w);
}
void _ud(int w,int l,int r,int ql,int qr) {
if(ql<=l&&r<=qr) {
op(s[w].sum)op(s[w].val)ope(s[w].t)
addtag(s[w],1);
ope(s[w].t)
return;
}
if(ql>r||qr<l) return;
int m=l+r>>1;
op(w)op(l)op(r)ope(s[w].t)
push(s[w],s[w<<1],s[w<<1|1]);
_ud(w<<1,l,m,ql,qr);
_ud(w<<1|1,m+1,r,ql,qr);
pull(s[w],s[w<<1],s[w<<1|1]);
op(l)op(r)ope(s[w].val)
}
void ud(int l,int r) {
op(l)ope(r)
_ud(1,0,n-1,l,r);
}
int qu(){
int an=s[1].val;
an=(an+mod)%mod;
return an;
}
};
namespace {
int n,m,N;
Graph g;
SEG seg;
};
void init(iint _N, iint _M, std::vector<iint> P, std::vector<iint> A) {
n=_N,m=_M;
N=n+m;
g=Graph(N);
REP1(i,N-1) {
g[P[i]].pb(i);
}
Vi sw(N,1);
auto dfs1=[&](auto dfs1,int u) ->void {
if(u>=n) return;
sw[u]=SZ(g[u]);
for(int v:g[u]) {
dfs1(dfs1,v);
(sw[u]*=sw[v])%=mod;
}
};
dfs1(dfs1,0);
Vi w(m);
auto dfs2=[&](auto dfs2,int u,int now) ->void {
if(u>=n) {
w[u-n]=now;
return;
}
Vi t,d;
t.pb(0),d.pb(1);
for(int v:g[u]) {
t.pb(v);
d.pb(sw[v]);
}
t.pb(0),d.pb(1);
int sz=SZ(g[u]);
Vi pd=d,sd=d;
REP1(i,sz) (pd[i]*=pd[i-1])%=mod;
RREP1(i,sz) (sd[i]*=sd[i+1])%=mod;
REP1(i,sz) dfs2(dfs2,t[i],(now*pd[i-1]%mod*sd[i+1]%mod));
};
dfs2(dfs2,0,1);
oparr(w)
Vi a(m);
REP(i,m) a[i]=A[i];
seg.init(m,a,w);
ope(seg.qu())
}
iint count_ways(iint L, iint R) {
int l=L-n,r=R-n;
seg.ud(l,r);
return seg.qu();
}
