#include <bits/stdc++.h>
#include "circuit.h"
using namespace std;
constexpr int64_t MOD = 1'000'002'022;
template <size_t L>
struct segment_tree
{
int64_t t[L << 1], sum[L << 1];
bitset<L << 1> lazy;
void propagate(size_t k)
{
if (lazy[k])
{
t[k << 1] = (sum[k << 1] - t[k << 1] + MOD) % MOD;
t[k << 1 | 1] = (sum[k << 1 | 1] - t[k << 1 | 1] + MOD) % MOD;
lazy[k << 1] = !lazy[k << 1];
lazy[k << 1 | 1] = !lazy[k << 1 | 1];
lazy[k] = 0;
}
}
void flip(size_t i, size_t j, size_t k = 1, size_t a = 0, size_t b = L - 1)
{
if (b < i || a > j)
return;
if (i <= a && b <= j)
{
lazy[k] = !lazy[k];
t[k] = (sum[k] - t[k] + MOD) % MOD;
}
else
{
propagate(k);
flip(i, j, k << 1, a, (a + b) >> 1);
flip(i, j, k << 1 | 1, ((a + b) >> 1) + 1, b);
t[k] = (t[k << 1] + t[k << 1 | 1]) % MOD;
}
}
void build_sum()
{
for (size_t i = L - 1; i; --i)
sum[i] = (sum[i << 1] + sum[i << 1 | 1]) % MOD;
}
};
constexpr size_t N = 200000, L = 1 << 18;
size_t n, m;
segment_tree<L> tree;
bitset<N> state;
vector<size_t> g[N];
int64_t num_children_prod[N];
void find_num_children_prod(size_t u)
{
if (g[u].empty())
{
num_children_prod[u] = 1;
return;
}
num_children_prod[u] = g[u].size();
for (auto const &v : g[u])
{
find_num_children_prod(v);
num_children_prod[u] = (num_children_prod[u] * num_children_prod[v]) % MOD;
}
}
void dfs(size_t u, int64_t prod = 1)
{
if (g[u].empty())
{
tree.sum[L + u] = prod;
return;
}
vector<int64_t> pre(g[u].size()), suf(g[u].size());
pre[0] = 1;
for (size_t i = 1; i < pre.size(); ++i)
pre[i] = (pre[i - 1] * num_children_prod[g[u][i - 1]]) % MOD;
suf[suf.size() - 1] = 1;
for (size_t i = suf.size() - 2; i < suf.size(); --i)
suf[i] = (suf[i + 1] * num_children_prod[g[u][i + 1]]) % MOD;
for (size_t i = 0; i < g[u].size(); ++i)
{
auto const &v = g[u][i];
dfs(v, (((prod * pre[i]) % MOD) * suf[i]) % MOD);
}
}
void init(int n_, int m_, vector<int> p, vector<int> a)
{
n = n_, m = m_;
for (size_t i = 0; i < p.size(); ++i)
if (p[i] != -1)
g[p[i]].push_back(i);
find_num_children_prod(0);
dfs(0);
tree.build_sum();
for (size_t i = 0; i < a.size(); ++i)
if (state[n + i] = a[i])
tree.flip(n + i, n + i);
}
int count_ways(int l, int r)
{
tree.flip(l, r);
return tree.t[1];
}
