#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pii;
typedef pair<ll, ll> pll;
#define ff first
#define ss second
ll ttt;
const ll INF=1e18;
const ll MOD=1e9+2022;
const ll N=200007;
ll n,m,k;
vector<ll>g[N];
vector<ll>p;
vector<ll>a;
ll tot[N];
ll dp[N];
bool lazy[2*N];
void push(int v){
if(lazy[v]){
dp[v]=tot[v]-dp[v];
dp[v]+=MOD;
dp[v]%=MOD;
lazy[2*(v+1)-1]=!lazy[2*(v+1)-1];
lazy[2*(v+1)]=!lazy[2*(v+1)];
lazy[v]=false;
}
}
void calc_tot(ll v){
if(!g[v].size()){tot[v]=1;return;}
tot[v]=g[v].size();
for(ll to:g[v]){
calc_tot(to);
tot[v]*=tot[to];
tot[v]%=MOD;
}
}
void calc_dp(ll v){
if(!g[v].size()){
dp[v]=a[v];
return;
}
for(ll to:g[v])calc_dp(to);
vector<ll>d;
ll cur=1;
for(ll to:g[v]){
d.push_back(cur);
cur*=tot[to];
cur%=MOD;
}
cur=1;
ll sum=0;
// cout<<"DDDDD\n";
for(ll i=g[v].size()-1;i>=0;i--){
// cout<<g[v][i]<<": "<<d[i]<<" ";
d[i]*=cur;
d[i]%=MOD;
// cout<<d[i]<<" ";
d[i]*=dp[g[v][i]];
d[i]%=MOD;
// cout<<d[i]<<endl;
sum+=d[i];
sum%=MOD;
cur*=tot[g[v][i]];
cur%=MOD;
}
dp[v]=sum;
}
void just_calc_dp(ll v){
push(v);
if(!g[v].size()){
// dp[v]=a[v];
return;
}
push(2*v);
push(2*v+1);
}
void update(int v, int tl, int tr, int l, int r){
push(v-1);
if(l>r)return;
if(tl==l&&tr==r){
// cout<<v-1<<": "<<tl<<" "<<tr<<endl;
lazy[v-1]=true;
push(v-1);
}
else{
int tm=(tl+tr)/2;
update(2*v,tl,tm,l,min(r,tm));
update(2*v+1,tm+1,tr,max(l,tm+1),r);
dp[v-1]=dp[2*v-1]*tot[2*v+1-1]+dp[2*v+1-1]*tot[2*v-1];
dp[v-1]%=MOD;
}
}
void init(int NN, int MM, vector<int> P, vector<int> A) {
n=NN;
m=MM;
for(ll v=1;v<n+m;v++){
g[P[v]].push_back(v);
// g[v].push_back(P[v]);
}
for(int x:P)p.push_back(x);
a.resize(n+m,0);
for(ll i=0;i<m;i++){
a[i+n]=A[i];
}
calc_tot(0);
calc_dp(0);
// for(int v=0;v<n+m;v++){
// push(v);
// cout<<v<<": "<<dp[v]<<endl;
// }
// for(ll v=0;v<n+m;v++){
// cout<<v<<": "<<tot[v]<<endl;
// }
}
int count_ways(int L, int R) {
// cout<<"______________\n";
update(1,0,m-1,L-n,R-n);
// for(int v=0;v<n+m;v++){
// push(v);
// cout<<v<<": "<<dp[v]<<endl;
// }
return dp[0];
}
