#include <iostream>
#include<bits/stdc++.h>
using namespace std;
std::vector<long long>VertexWeight;
vector<vector<long long>>Children;
vector<long long> Combinations;
vector<pair<long long, long long>> SegTree;
vector<bool> Inverted;
vector<int> On;
int Nb;
long long GetProductExcept(long long excp,long long n,long long x,long long y,vector<long long>& Wmults){
if(y>excp && x>excp){
return Wmults[n];
}
if(y<excp && x<excp){
return Wmults[n];
}
if(y==excp && x==excp){
return 1;
}
return (GetProductExcept(excp,n*2+1,(y+x)/2+1,y,Wmults)*GetProductExcept(excp,n*2,x,(y+x)/2,Wmults))%1000002022;
}
void Build(long long mult,long long val,long long n,long long x,long long y,vector<long long>& Wmults){
if(y>val && x>val){
return;
}
if(y<val && x<val){
return;
}
if(x==y && x==val){
Wmults[n]=(Wmults[n]*mult)%1000002022;
return;
}
Wmults[n]=(Wmults[n]*mult)%1000002022;
Build(mult,val,n*2,x,(y+x)/2,Wmults);
Build(mult,val,n*2+1,(y+x)/2+1,y,Wmults);
return;
}
long long Switch(long long l,long long r,long long n,long long x,long long y){
if(x>r){
return SegTree[n].second;
}
if(l>y){
return SegTree[n].second;
}
if(x>=l && y<=r){
Inverted[n]=!Inverted[n];
SegTree[n]={SegTree[n].first,((SegTree[n].first-SegTree[n].second)%1000002022+1000002022)%1000002022};
return SegTree[n].second;
}
if(Inverted[n]){
SegTree[n*2]={SegTree[n*2].first,((SegTree[n*2].first-SegTree[n*2].second)%1000002022+1000002022)%1000002022};
SegTree[n*2+1]={SegTree[n*2+1].first,((SegTree[n*2+1].first-SegTree[n*2+1].second)%1000002022+1000002022)%1000002022};
Inverted[n]=false;
Inverted[n*2]=!Inverted[n*2];
Inverted[n*2+1]=!Inverted[n*2+1];
}
long long vala=Switch(l,r,n*2,x,(y+x)/2);
long long valb=Switch(l,r,n*2+1,(y+x)/2+1,y);
long long val=(vala+valb)%1000002022;
SegTree[n]={SegTree[n].first,val};
return val;
}
void MakeSegTree(long long enabled,long long mult,long long pos,long long n,long long x,long long y){
if(y>=pos && pos>=x){
SegTree[n]={(SegTree[n].first+mult)%1000002022,(SegTree[n].second+mult*enabled)%1000002022};
}
if(pos>y){
return;
}
if(pos<x){
return;
}
if(x!=y){
MakeSegTree(enabled,mult,pos,2*n,x,(x+y)/2);
MakeSegTree(enabled,mult,pos,2*n+1,(x+y)/2+1,y);
}
return;
}
void AssingWeights(long long pos, long long baseMult){
if(Children[pos].size()==0){
VertexWeight[pos]=baseMult;
return;
}
if(Children[pos].size()==1){
AssingWeights(Children[pos][0],baseMult);
return;
}
long long NumChild=Children[pos].size();
vector<long long> Wmults(4*NumChild,1);
for(long long i=0;i<NumChild;i++){
Build(Combinations[Children[pos][i]],i,1,0,NumChild+1,Wmults);
}
for(long long i=0;i<NumChild;i++){
long long extraMult=(GetProductExcept(i,1,0,NumChild+1,Wmults)*baseMult)%1000002022;
AssingWeights(Children[pos][i],extraMult);
}
}
void init(int N, int M, vector<int> P, vector<int> A){
Nb=N;
Combinations=vector<long long>(N+M);
Children=vector<vector<long long>>(N+M);
VertexWeight=vector<long long>(N+M);
for(long long i=M+N-1;i>0;i--){
long long comb=max((long long)1,(long long)Children[i].size());
for(long long j=0;j<Children[i].size();j++){
comb=(comb*Combinations[Children[i][j]])%1000002022;
}
Combinations[i]=comb;
Children[P[i]].push_back(i);
}
AssingWeights(0,1);
SegTree=vector<pair<long long,long long>>(4*(M+N));
Inverted=vector<bool>(4*(M+N));
On=A;
for(long long j=0;j<M;j++){
MakeSegTree(A[j],VertexWeight[j+N],j+N,1,0,N+M+1);
}
Nb=N+M+1;
}
int count_ways(int L, int R){
return Switch(L,R,1,0,Nb);
}
