#include <bits/stdc++.h>
using namespace std;
#define ll long long
constexpr ll MOD = 1000002022;
constexpr int MAXN = 2e5 + 5;
vector<int> adj[MAXN];
pair<ll, ll> dp[MAXN]; // attivo, spento
bool lazy[MAXN]; // attivo, spento
int N, M;
vector<int> A;
vector<int> P;
int PW;
bool is_seg = 0;
vector<ll> mult(vector<ll> &a, vector<ll> &b) { // b size è il minore ed è sempre 2
int dim = (a.size() - 1) + (b.size() - 1) + 1;
vector<ll> res(dim);
for (int i = 0; i < a.size(); i ++) {
for (int j = 0; j < b.size(); j ++) {
int sum = (i + j < dim) ? i + j : i + j - dim;
res[sum] += (a[i] * b[j]) % MOD;
res[sum] %= MOD;
}
}
return res;
}
void dfs(int u) {
if (u >= N) return;
vector<ll> poly;
poly.push_back(1);
for (auto x : adj[u]) {
dfs(x);
auto [acceso, spento] = dp[x];
vector<ll> curr_poly = {spento, acceso};
poly = mult(poly, curr_poly);
}
ll acceso = 0;
ll spento = 0;
for (int i = 0; i < poly.size(); i ++) {
acceso += (poly[i] * i) % MOD;
acceso %= MOD;
spento += (poly[i] * (poly.size() - 1 - i)) % MOD;
spento %= MOD;
}
dp[u] = {acceso, spento};
}
pair<ll, ll> merge(int a, int b) {
vector<ll> poly_a = {dp[a].second, dp[a].first};
vector<ll> poly_b = {dp[b].second, dp[b].first};
vector<ll> poly = mult(poly_a, poly_b);
ll acceso = 0;
ll spento = 0;
for (int i = 0; i < poly.size(); i ++) {
acceso += (poly[i] * i) % MOD;
acceso %= MOD;
spento += (poly[i] * (poly.size() - 1 - i)) % MOD;
spento %= MOD;
}
return {acceso, spento};
}
void init(int N, int M, vector<int> P, vector<int> A) {
:: N = N;
:: M = M;
:: A = A;
:: P = P;
:: PW = M;
for (int i = 1; i < N + M; i ++) {
adj[P[i]].push_back(i);
}
if (M == N + 1 && (M & (M - 1)) == 0) is_seg = 1;
if (is_seg) {
for (int i = 0; i < PW; i ++) dp[PW + i] = {A[i], A[i] ^ 1};
for (int i = PW - 1; i >= 1; i --) dp[i] = merge(2 * i, 2 * i + 1);
fill(lazy, lazy + MAXN, 0);
}
}
void push_lazy(int idx) {
if (lazy[idx] == 0) return;
lazy[idx] = 0;
auto [acceso, spento] = dp[idx];
dp[idx] = {spento, acceso};
if (idx >= PW) return;
lazy[2 * idx] ^= 1;
lazy[2 * idx + 1] ^= 1;
}
void update(int idx, int l, int r, int ql, int qr) {
// cout << "idx, l, r, ql, qr : " << idx << " " << l << " " << r << " " << ql << " " << qr << '\n';
push_lazy(idx);
if (ql <= l && r <= qr) {
lazy[idx] = 1;
push_lazy(idx);
return;
}
if (r <= ql || qr <= l) return;
push_lazy(idx);
update(2 * idx , l, (l + r) / 2, ql, qr);
update(2 * idx + 1, (l + r) / 2, r, ql, qr);
dp[idx] = merge(2 * idx, 2 * idx + 1);
}
int count_ways(int L, int R) {
if (!is_seg) {
for (int i = L - N; i <= R - N; i ++) {
A[i] ^= 1;
}
for (int i = 0; i < M; i ++) {
dp[N + i] = {A[i], A[i] ^ 1};
}
dfs(0);
return dp[0].first;
}
else {
update(1, 0, PW, L - N, R + 1 - N);
return dp[1].first;
}
}
