#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#include <immintrin.h>
#pragma GCC target("avx512vl,bmi,bmi2,lzcnt,popcnt")
using namespace std;
typedef __m512i vi;
typedef unsigned long long ull;
#include "circuit.h"
const int MAX=200025,mod=(1e9)+2022;
int cont[MAX],val[MAX],state[MAX],n,m;
unsigned long long State[MAX/64+1];
vi Cont[MAX/16+2];
vector<vector<int>>adj;
void dfs(int v){
    if(v>=n){
        val[v]=1;
        return;
    }
    int sz=adj[v].size();
    val[v]=sz;
    for(auto&u:adj[v]){
        dfs(u);
        val[v]=(val[v]*1LL*val[u])%mod;
    }
}
void dfs(int v,int cur){
    if(v>=n){
        cont[v-n]=cur;
        return;
    }
    int sz=adj[v].size();
    int pre[sz],suf[sz];
    for(int i=0;i<sz;i++)suf[i]=pre[i]=val[adj[v][i]];
    for(int i=1;i<sz;i++)pre[i]=(pre[i]*1LL*pre[i-1])%mod;
    for(int i=sz-2;i>=0;i--)suf[i]=(suf[i]*1LL*suf[i+1])%mod;
    for(int i=0;i<sz;i++){
        int nw=cur;
        if(i)nw=(nw*1LL*pre[i-1])%mod;
        if(i+1<sz)nw=(nw*1LL*suf[i+1])%mod;
        dfs(adj[v][i],nw);
    }
}
void init(int N,int M,vector<int>P,vector<int>A){
    n=N;m=M;
    adj.resize(N+M);
    for(int i=1;i<N+M;i++)adj[P[i]].push_back(i);
    for(int i=0;i<M;i++)state[i]=A[i];
    dfs(0);
    dfs(0,1);
    for(int i=0;i<M;i++)State[i>>6]|=(((ull)state[i])<<(i&63));
    for(int i=0;i<M;i+=16)Cont[i>>6]=_mm512_loadu_si512((vi*)&cont[i]);
}
int count_ways(int L, int R) {
    L-=n;R-=n;
    int bl=(L>>6),br=(R>>6);
    if(bl==br){
        ull mask=(1ULL<<(R&63))-(1ULL<<(L&63));
        mask+=(1ULL<<(R&63));
        State[bl]^=mask;
    }else{
        ull mask=ULLONG_MAX - ((1ULL<<L)-1);
        State[bl]^=mask;bl++;
        mask=(2ULL<<(R&63)) - 1;
        State[br]^=mask;
        for(int i=bl;i<br;i++)State[i]^=ULLONG_MAX;
    }
    vi ans=_mm512_setzero_epi32(),temp;
    vi MOD=_mm512_set1_epi32(mod);
    vi zero=_mm512_setzero_epi32();
    int sz=(m-1)>>16;
    for(int i=0;i<=sz;i++){
        ans=_mm512_add_epi32(ans,_mm512_mask_blend_epi32((State[i>>2]>>((i&3)*16))&UINT16_MAX,Cont[i],zero));
        temp=_mm512_sub_epi32(ans,MOD);
        ans=_mm512_mask_blend_epi32(_mm512_cmpge_epi32_mask(ans,MOD),ans,temp);
    }
    int arr[16]={};
    _mm512_storeu_si512((vi*)arr,ans);
    return accumulate(arr,arr+16,0LL)%mod;
}