#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod=1'000'002'022;
long long pot2[200010];
long long iloL[200010], iloR[200010], ilo[200010];
vector<int>graf[200010];
long long policz(int n){
return pot2[n-1];
}
long long wsp[200010];
void dfs1(int x){
ilo[x] = 1;
if(graf[x].size())
ilo[x] = graf[x].size();
for(auto j: graf[x]){
dfs1(j);
ilo[x] = ilo[j]*ilo[x]%mod;
}
long long pom = 1;
for(int i=0;i<(int)graf[x].size();i++){
pom = pom*ilo[graf[x][i]]%mod;
iloL[graf[x][i]] = pom;
}
pom = 1;
for(int i=(int)graf[x].size()-1;i>=0;i--){
pom = pom*ilo[graf[x][i]]%mod;
iloR[graf[x][i]] = pom;
}
}
void dfs(int x, long long ilo){
if(graf[x].size()==0){
wsp[x] = ilo;
}
for(int i=0;i<(int)graf[x].size();i++){
long long pom = ilo;
if(i!=0)
pom = (pom*iloL[graf[x][i-1]])%mod;
if(i!=(int)graf[x].size()-1)
pom = (pom*iloR[graf[x][i+1]])%mod;
dfs(graf[x][i], pom);
}
}
struct node{long long val1, val2;bool czy;};
const int base = 1<<17;
node tree[2*base];
int M, N;
void change(int w, int l, int p, int a, int b){
if(l>b || p<a)return;
if(a<=l && p<=b){
swap(tree[w].val1, tree[w].val2);
tree[w].czy^=1;
return;
}
if(tree[w].czy){
swap(tree[w*2].val1, tree[w*2].val2);
swap(tree[w*2+1].val1, tree[w*2+1].val2);
tree[w*2].czy^=1;
tree[w*2+1].czy^=1;
tree[w].czy = 0;
}
change(w*2, l, (l+p)/2, a, b);
change(w*2+1, (l+p)/2+1, p, a, b);
tree[w].val1 = tree[w*2].val1+tree[w*2+1].val1;
tree[w].val2 = tree[w*2].val2+tree[w*2+1].val2;
}
void init(int n, int m, std::vector<int> P, std::vector<int> A) {
M = m;
N = n;
int i;
pot2[0] = 1;
for(int i=1;i<=n+m;i++)pot2[i] = pot2[i-1]*2%mod;
for(int i=1;i<n+m;i++)
graf[P[i]].push_back(i);
wsp[0] = 1;
dfs1(0);
dfs(0, 1);
// for(i=0;i<m;i++)
// printf("%lld ", wsp[i+n]);printf("\n");
// for(i=0;i<m+n;i++)
// printf("%lld ", ilo[i]);printf("\n");
for(int i=0;i<m;i++){
tree[i+base].val1 = wsp[i+n]*A[i];
tree[i+base].val2 = wsp[i+n]*(A[i]^1);
}
for(int i=base-1;i>0;i--){
tree[i].val1 = (tree[i*2].val1+tree[i*2+1].val1)%mod;
tree[i].val2 = (tree[i*2].val2+tree[i*2+1].val2)%mod;
}
// for(int i=0;i<M;i++)
// printf("%lld ", tree[i+base].val1);printf("\n");
}
int count_ways(int L, int R) {
change(1, 0, base-1, L-N, R-N);
return tree[1].val1%mod;
}
