#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod=1'000'002'022; // ?????
const int N = 1e5+10;
vector<int> child[N];
long long total[N];
long long contrib[N];
void dfs(int at) {
total[at] = max(1, (int)child[at].size());
for(int to:child[at]) {
dfs(to);
total[at] = (total[at] * total[to])%mod;
}
}
void dfs2(int at) {
long long sumtot = 0;
for(int to:child[at]) {
sumtot+=total[to];
sumtot%=mod;
}
int c = child[at].size();
long long pref[c];
pref[0] = 1;
for(int i = 1;i<c;i++) {
pref[i] = (pref[i-1] * total[child[at][i-1]])%mod;
}
long long suff = 1;
for(int i = c-1;i>=0;i--) {
contrib[child[at][i]] = (((suff*pref[i])%mod)*contrib[at])%mod;
dfs2(child[at][i]);
suff = (suff*total[child[at][i]]);
}
}
vector<int> A;
int nn;
void init(int n, int m, std::vector<int> p, std::vector<int> a) {
nn=n;
A = a;
for(int i = 1;i<m+n;i++) {
child[p[i]].push_back(i);
}
for(int i= 0;i<m+n;i++)contrib[i] = 1;
dfs(0);
dfs2(0);
}
int count_ways(int L, int R) {
L-=nn, R-=nn;
for(int i = L;i<=R;i++)A[i]^=1;
long long sum = 0;
for(int i = 0;i<(int)A.size();i++) {
sum=(sum+(1-A[i])*contrib[nn+i])%mod;
}
int ans = (total[0]-sum)%mod;
return ans;
}
