#include "circuit.h"
#include <iostream>
#include <numeric>
#include <algorithm>
#include <vector>
using namespace std;
// If only one the inputs is turned on, vastaus on tulo kaikista / (tulo polulla olevista)
// If all of the inputs are turned on, vastaus on tulo kaikista.
// If two of the inputs are turned on, vastaus on 2 * tulo kaikista / (tulo poluilla (juureen) olevista)
// If three inputs are turned on, vastaus on 2 * tulo kaikista / (tulo poluilla (juureen) olevista)
// |
// | all / 1-path
// |
// 1
//
// |
// |
// |
// x
// / \
// / \ all / 1-path + all / 2-path - all / union + all / union = all / 1-path + all / 2-path
// / \ |---------------------------------------| |----------|
// 1 2 c_x = 1 c_x = 2
//
//
// |
// |
// | all / 1-path + all / 2-path + all / 3-path - all / 12-path - all / 13-path - all / 13-path + all / 123-path
// x |-------------------------------------------------------------------------------------------------------------|
// / \ c_x = 1
// / | \ all / 12-path + all / 13-path + all / 23-path - all / 123-path * 2
// / | \ |----------------------------------------------------------------|
// 1 2 3 c_x = 2
// all / 123-path
// |------------|
// c_x = 3
const int M = 1'000'002'022;
using i64 = long long;
vector<vector<int>> children;
vector<int> a;
vector<int> dp;
int add(int a, int b) {
a += b;
if (a >= M) a -= M;
return a;
}
int mul(int a, int b) {
return i64(a) * b % M;
}
int prod_dfs(int u) {
int prod = children[u].empty() ? 1 : children[u].size();
for (int v : children[u]) {
prod = mul(prod, prod_dfs(v));
}
dp[u] = prod;
return prod;
}
vector<int> oth_value;
void dfs(int u, int oth) {
oth_value[u] = oth;
vector<int> values{1};
for (int v : children[u]) {
values.push_back(dp[v]);
}
values.push_back(1);
reverse(values.begin(), values.end());
vector<int> rvalues = values;
partial_sum(values.begin(), values.end(), values.begin(), mul);
partial_sum(rvalues.rbegin(), rvalues.rend(), rvalues.rbegin(), mul);
values.pop_back();
for (int v : children[u]) {
values.pop_back();
int value = mul(oth, mul(values.back(), rvalues.back()));
dfs(v, value);
rvalues.pop_back();
}
}
int n;
void init(int n, int m, vector<int> p, vector<int> a) {
children.resize(n + m);
for (int i = 1; i < n + m; ++i) {
children[p[i]].push_back(i);
}
dp.assign(n + m, 0);
oth_value.assign(n + m, 0);
prod_dfs(0);
dfs(0, 1);
oth_value = vector<int>(oth_value.begin() + n, oth_value.end());
::n = n;
::a = a;
}
int count_ways(int l, int r) {
l -= n;
r -= n;
for (int i = l; i <= r; ++i) {
a[i] ^= 1;
}
int ans = 0;
for (int i = 0; i < (int) a.size(); ++i) {
if (a[i]) {
ans = add(ans, oth_value[i]);
}
}
return ans;
}
