/**
* I nearly fully-solved this problem in IOI 2022, though I ran out of time. Initially, I
* was only hoping to score more partials, but it turned out to be a full solution.
*
* For [S1-3], DFS + dp suffice: for each node u in the tree, we compute dp1[u], the num of
* different assignments of parameters to threshold gates in the subtree of u that will
* result in u being 1. Similarly, we can define dp0[u].
* Let v_1, v_2, ..., v_k be all the children of u. Mathematically,
* dp1[u] = (dp1[v_1] * dp1[v_2] * ... * dp1[v_k]) * k <-- k options for u
* --> + (dp1[v_1] * ... * dp1[v_{k-1}] * dp0[v_k])
* (k-1) options for u --> + ...
* --> + dp0[v_1] * dp1[v_2] * ... * dp1[v_k]) * (k-1)
* + ...,
* and dp0[u] can be found from dp1[u].
*
* The huge sum can be computed quite efficiently, again with dp. For each node u, let
* partial[i] (0 <= i <= k) be
* sum{ (dp0[v_1] or dp1[v_1]) * ... * (dp0[v_k] or dp1[v_k]) : exactly i dp1[]'s }.
* We can find each partial[i] iteratively:
* partial[i] <-- partial[i] * dp0[some_v] + partial[i-1] * dp1[some_v].
* Therefore, dp1[u] = partial[1] * 1 + ... + partial[k] * k. So, O((N+M)^2 * Q). [S4] can
* be solved too, because we only have to update O(log(N)) dp1[]'s and dp0[]'s in each
* query.
*
* I thought there must be ways to optimize this dp. Because the source gates can receive
* arbitrary input, I tried out some examples; for each one of them, I use a variable to
* denote each source gate and try to find the expression for each gate on paper. I noticed
* a pattern, but didn't bother to prove it in the contest. Anyway, let's begin.
* Let f(x) = (dp1[v_1] * x + dp0[v_1])...(dp1[v_k] * x + dp0[v_k]), then
* partial[i] = coefficient of x^i in f(x). Write f(x) as c_0 + c_1 * x + ... + c_k * x^k.
* We have
* f'(x) = 1 * c_1 + 2 * c_2 * x + 3 * c_3 * x^2 + ... + k * c_k * x^{k-1},
* which means
* dp[u] = c_1 + 2 * c_2 + ... + k * c_k
* = f'(1)
* = sum{ dp1[v_i] * prod{ (dp1[v_j] + dp0[v_j]) : j != i } : 1 <= i <= k }
* = sum{ dp[v_i] * prod{ sub[v_j] : j != i } }.
* Here, sub[v] is the num of comb of freely choosing all thresholds in the subtree of v.
* This quantity can be easily found with DFS. The trick is pretty well-known, at least
* in the Olympiad maths circle.
*
* After doing some more examples on my scratch paper, I noticed that the formula we
* obtained above implies that dp[1] is a linear combination of
* dp[N], dp[N+1], ..., dp[N+M-1], i.e. the inputs. Nice! It remains to compute the
* coefficient of each input in the final linear comb of dp[1], and use
* a segment tree with lazy propagation.
*
* Overall, I'd say this is a pretty interesting problem, at least with the parts of dp &
* maths. The portion of handling queries with seg tree + lazy is definitely a bit
* mechanical, but still tests a contestant's data structure skills. Note that the MOD is
* not a prime! Therefore, dp[u] cannot be sum{ dp[v_i] / sub[v_i] } * prod{ sub[v_i] },
* cuz a multiplicative inverse may not exist under mod 1000002022. The issue can be
* resolved by computing the suffix product and prefix product of sub[].
*
* Time Complexity: O(N + (M + Q) * log(M)) (Full solution)
* Implementation 1 (DP, maths, segment tree, lazy propagation)
*/
#include <bits/stdc++.h>
#include "circuit.h"
typedef long long ll;
typedef std::vector<int> vec;
const ll MOD = 1000002022;
// Our toggleable linear combination segment tree (using lazy propagation) (lol)
class TogLincomb {
private:
int m;
std::vector<ll> pre_coeff;
std::vector<ll> tree;
std::vector<bool> lazy; // whether the range has been lazily toggled
inline void flip(int k, int i, int j) {
tree[k] = (pre_coeff[j + 1] - pre_coeff[i]) - tree[k], lazy[k] = 1 - lazy[k];
tree[k] = (tree[k] % MOD + MOD) % MOD;
}
inline void push(int k, int i, int j) {
if (lazy[k]) {
int mid = (i + j) / 2;
flip(2 * k, i, mid);
flip(2 * k + 1, mid + 1, j);
}
lazy[k] = false;
}
void _toggle(int l, int r, int k, int i, int j) {
if (i > r || l > j || l > r)
return;
if (i == l && j == r) {
flip(k, i, j);
return;
}
int mid = (i + j) / 2;
push(k, i, j);
_toggle(l, std::min(r, mid), 2 * k, i, mid);
_toggle(std::max(l, mid + 1), r, 2 * k + 1, mid + 1, j);
tree[k] = tree[2 * k] + tree[2 * k + 1], tree[k] %= MOD;
}
public:
TogLincomb() {}
TogLincomb(int size, const std::vector<ll>& coeff) {
m = size;
pre_coeff.assign(m + 1, 0);
for (int k = 0; k < m; k++)
pre_coeff[k + 1] = pre_coeff[k] + coeff[k], pre_coeff[k + 1] %= MOD;
tree.assign(4 * m, 0);
lazy.assign(4 * m, false);
}
void toggle(int l, int r) { _toggle(l, r, 1, 0, m - 1); }
ll sum() { return tree[1]; }
};
int n;
std::vector<vec> tree;
std::vector<ll> dp, sub;
TogLincomb seg_tree;
void pre_comp(int k) {
sub[k] = 1;
if (k >= n)
return;
for (int child : tree[k]) {
pre_comp(child);
sub[k] *= sub[child], sub[k] %= MOD;
}
sub[k] *= int(tree[k].size()), sub[k] %= MOD;
}
void compute(int k) {
int c = tree[k].size();
std::vector<ll> prefix(c + 1), suffix(c + 1);
prefix[0] = suffix[c] = 1;
for (int i = 0, j = c - 1; i < c; i++, j--) {
prefix[i + 1] = prefix[i] * sub[tree[k][i]] % MOD;
suffix[j] = suffix[j + 1] * sub[tree[k][j]] % MOD;
}
for (int i = 0; i < c; i++) {
int child = tree[k][i];
dp[child] = dp[k] * prefix[i] % MOD * suffix[i + 1] % MOD;
compute(child);
}
}
void init(int N, int m, vec P, vec A) {
n = N;
tree.assign(n + m, vec());
for (int k = 1; k < n + m; k++)
tree[P[k]].push_back(k);
sub.resize(n + m);
pre_comp(0);
dp.resize(n + m);
dp[0] = 1;
compute(0);
seg_tree = TogLincomb(m, std::vector<ll>(dp.begin() + n, dp.end()));
for (int k = 0; k < m; k++) {
if (A[k])
seg_tree.toggle(k, k);
}
}
int count_ways(int l, int r) {
seg_tree.toggle(l - n, r - n);
return int(seg_tree.sum());
}
