#include "circuit.h"
#include <bits/stdc++.h>
#define fs first
#define sc second
using namespace std;
const int mod=1000002022;
void add(int& x,int y){
x+=y;
x-=mod*(x>=mod);
}
int mul(int x,int y){
return 1ll*x*y%mod;
}
int po(int x,int y){
int z=1;
while(y){
if(y&1){
z=mul(z,x);
}
x=mul(x,x);
y>>=1;
}
return z;
}
int inv(int x){
return po(x,222*2242156-1);
}
vector<int> g,a;
struct ST{
struct no{
int sum=0,ans=0,tag=0;
};
vector<no> st;
void init(int x){
st.resize(4*x);
}
void upd(int v){
st[v].ans=(st[v].sum-st[v].ans+mod)%mod;
st[v].tag^=1;
}
void pudo(int v){
if(st[v].tag){
upd(2*v+1);
upd(2*v+2);
st[v].tag=0;
}
}
void pull(int v){
st[v].ans=(st[2*v+1].ans+st[2*v+2].ans)%mod;
}
void build(int v,int L,int R){
if(L==R){
st[v].sum=g[L];
st[v].ans=st[v].sum*a[L];
return;
}
int m=(L+R)/2;
build(2*v+1,L,m);
build(2*v+2,m+1,R);
pull(v);
st[v].sum=(st[2*v+1].sum+st[2*v+2].sum)%mod;
}
void toggle(int v,int L,int R,int l,int r){
if(L==l && r==R){
upd(v);
return;
}
pudo(v);
int m=(L+R)/2;
if(r<=m){
toggle(2*v+1,L,m,l,r);
}
else if(l>m){
toggle(2*v+2,m+1,R,l,r);
}
else{
toggle(2*v+1,L,m,l,m);
toggle(2*v+2,m+1,R,m+1,r);
}
pull(v);
}
int query(){
return st[0].ans;
}
}st;
const int x[2]={2,223};
int cnt[2]={0};
int pe=1;
int n,m;
struct tn{
vector<int> ch;
int deg=0;
int cs[2]={0};
int dx=1;
};
vector<tn> v;
void dfs(int r,int a,int b,int c){
if(r>=n){
int z=mul(pe,inv(c));
z=mul(z,po(2,cnt[0]-a));
z=mul(z,po(223,cnt[1]-b));
g[r-n]=z;
return;
}
for(auto h:v[r].ch){
dfs(h,a+v[r].cs[0],b+v[r].cs[1],mul(c,v[r].dx));
}
}
void init(int N, int M, vector<int> p, vector<int> A) {
n=N;
m=M;
a=A;
st.init(m);
g.resize(m);
v.resize(n+m);
for(int i=1;i<n+m;i++){
v[p[i]].ch.push_back(i);
v[p[i]].deg++;
}
for(int i=0;i<n;i++){
int s=v[i].deg;
while(s%2==0){
s/=2;
v[i].cs[0]++;
cnt[0]++;
}
while(s%223==0){
s/=223;
v[i].cs[1]++;
cnt[1]++;
}
v[i].dx=s;
pe=mul(pe,s);
}
dfs(0,0,0,1);
st.build(0,0,m-1);
}
int count_ways(int L, int R) {
st.toggle(0,0,m-1,L-n,R-n);
return st.query();
}
