#include "circuit.h"
#include <iostream>
#include <numeric>
#include <algorithm>
#include <vector>
using namespace std;
const int M = 1'000'002'022;
using i64 = long long;
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;
}
struct Tree {
vector<int> sum, flip_sum, tag;
void init(int n) {
sum.resize(n * 4);
flip_sum.resize(n * 4);
tag.resize(n * 4);
}
void change(int s, int l, int r, int k, int x) {
if (r - l == 1) {
sum[s] = x;
return;
}
push(s);
int m = (l + r) / 2;
if (k < m) change(s * 2 + 0, l, m, k, x);
else change(s * 2 + 1, m, r, k, x);
sum[s] = add(sum[s * 2], sum[s * 2 + 1]);
flip_sum[s] = add(flip_sum[s * 2], flip_sum[s * 2 + 1]);
}
void flip(int s, int l, int r, int ql, int qr) {
if (r <= ql || qr <= l) return;
if (ql <= l && r <= qr) return apply(s);
push(s);
int m = (l + r) / 2;
flip(s * 2 + 0, l, m, ql, qr);
flip(s * 2 + 1, m, r, ql, qr);
sum[s] = add(sum[s * 2], sum[s * 2 + 1]);
flip_sum[s] = add(flip_sum[s * 2], flip_sum[s * 2 + 1]);
}
void push(int s) {
if (tag[s]) {
apply(s * 2 + 0);
apply(s * 2 + 1);
tag[s] = 0;
}
}
void apply(int s) {
swap(flip_sum[s], sum[s]);
tag[s] ^= 1;
}
};
vector<vector<int>> children;
vector<int> a;
vector<int> dp;
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, m;
Tree seg;
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);
::n = n;
::m = m;
::a = a;
seg.init(m);
for (int i = 0; i < m; ++i) {
seg.change(1, 0, m, i, oth_value[i + n]);
if (a[i] == 0) {
seg.flip(1, 0, m, i, i + 1);
}
}
}
int count_ways(int l, int r) {
l -= n;
r -= n;
seg.flip(1, 0, m, l, r + 1);
return seg.sum[1];
}
