#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
const long long mod=1'000'002'022; // ?????
const int N = 2e5+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) {
if(!child[at].size())return;
long long sumtot = 0;
for(int to:child[at]) {
sumtot+=total[to];
sumtot%=mod;
}
int c = child[at].size();
vector<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]])%mod;
}
}
vector<int> A;
int nn;
pair<long long, long long> T[4*N];
int lz[4*N];
void build(vector<int> &a, int tl = 0, int tr = N-1, int v = 1) {
if(tl == tr) {
if((int)a.size() > tl)T[v] = {a[tl], 0};
else T[v] = {0, 0};
return;
}
int tm = (tl+tr)/2;
build(a, tl, tm, 2*v);
build(a, tm+1, tr, 2*v+1);
T[v].first = (T[2*v].first + T[2*v+1].first)%mod;
T[v].second = (T[2*v].second + T[2*v+1].second)%mod;
}
void push(int v) {
if(lz[v]) {
lz[v] = 0;
lz[2*v]^=1;
lz[2*v+1]^=1;
swap(T[2*v].first, T[2*v].second);
swap(T[2*v+1].first, T[2*v+1].second);
}
}
void update(int l, int r, int tl = 0, int tr = N-1, int v = 1) {
if(r < tl or tr < l)return;
if(l<=tl and tr<=r) {
lz[v] ^= 1;
swap(T[v].first, T[v].second);
return;
}
push(v);
int tm = (tl+tr)/2;
update(l, r, tl, tm, 2*v);
update(l, r, tm+1, tr, 2*v+1);
T[v].first = (T[2*v].first + T[2*v+1].first)%mod;
T[v].second = (T[2*v].second + T[2*v+1].second)%mod;
}
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);
vector<int> cont(m);
for(int i = 0;i<m;i++) {
cont[i] = contrib[i+n];
}
build(cont);
for(int i = 0;i<m;i++) {
if(A[i]) {
update(i, i);
}
}
}
int count_ways(int L, int R) {
L-=nn, R-=nn;
update(L, R);
long long ans = (total[0] - T[1].first)%mod;
ans+=mod;
ans%=mod;
return ans;
}
