#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
int MOD=1000002022;
vector<int> allprod; //for each node, product of all threshold totals in subtree of the node
vector<int> subt_values; //for each node, product of all threshold totals not on path from node to root
vector<vector<int>> children;
vector<int> ison;
int dfs2currentprod = 1; //the current product of the dfs2 values
int curS = 0;
int n,m;
void dfs1(int node) {
allprod[node] = 1;
for (int j:children[node]) {
dfs1(j);
allprod[node] *= allprod[j];
allprod[node]%=MOD;
}
if (children[node].size()) allprod[node]*=children[node].size();
allprod[node]%=MOD;
}
void dfs2(int node) {
//calculate the product of all threshold totals not on the path from node to root, for each leaf
if (!children[node].size()) {
subt_values[node] = dfs2currentprod;
return;
}
int oldprod = dfs2currentprod;
int k=children[node].size();
vector<int> prefprod(k+1,1); //product of sub product for all children with index<i
for (int i=1; i<=k; i++) {
prefprod[i] = prefprod[i-1]*allprod[children[node][i-1]];
prefprod[i]%=MOD;
}
vector<int> suffprod(k+1,1); //product of sub product for all children with index>=i
for (int i=k-1; i>=0; i--) {
suffprod[i] = suffprod[i+1]*allprod[children[node][i]];
suffprod[i]%=MOD;
}
/*cout << "DFS " << node << " " << dfs2currentprod;
for (int i=0; i<k+1; i++) {
cout << i <<" " << prefprod[i] <<" " << suffprod[i] << endl;
}*/
for (int i=0; i<k; i++) {
int totprod=prefprod[i]*suffprod[i+1];
totprod%=MOD;
totprod*=oldprod;
totprod%=MOD;
dfs2currentprod = totprod;
dfs2(children[node][i]);
}
}
void init(int32_t N, int32_t M, vector<int32_t> P, vector<int32_t> A) {
n=N;
m=M;
allprod = vector<int>(N+M, 1);
subt_values = vector<int>(N+M, 1);
ison = vector<int>(M, 1);
children=vector<vector<int>>(N+M);
for (int i=1; i<N+M; i++) {
children[P[i]].push_back(i);
}
dfs1(0);
dfs2(0);
/*for (int i=0; i<N+M; i++) {
cout << i <<" " << allprod[i] << endl;
}
for (int i=0; i<N+M; i++) {
cout << i <<" " << subt_values[i] << endl;
}*/
for (int i=N; i<N+M; i++) {
ison[i-N] = A[i-N];
}
}
/*3 6 5
-1 0 0 1 1 1 2 2 0
0 0 0 0 0 0
3 8*/
int32_t count_ways(int32_t L, int32_t R) {
for (int i=L; i<=R; i++) {
ison[i-n] = 1-ison[i-n];
}
int su=0;
for (int i=0; i<m; i++) {
//cout << i <<" " << subt_values[i+n] << endl;
su+=ison[i]*subt_values[i+n];
su%=MOD;
}
return su;
}
