#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000002022;
const int MAXN = 4e5 + 1;
int A[MAXN];
vector<int> adj[MAXN];
int N, M;
array<ll, 2> dp[MAXN];
int lazy[MAXN];
int depth[MAXN];
ll exp(ll a, ll b) {
ll res = 1;
while (b > 0) {
if (b & 1) {
res = res * a % MOD;
}
a = a * a % MOD;
b /= 2;
}
return res;
}
void upd(int i) {
if (lazy[i] == 0) return;
if (2 * i + 1 < MAXN) {
lazy[i * 2] ^= 1;
lazy[i * 2 + 1] ^= 1;
}
lazy[i] = 0;
swap(dp[i][0], dp[i][1]);
}
void update(int i, int l, int r, int ql, int qr) {
upd(i);
if (ql > r || l > qr) return;
// cout << l << " " << r << "\n";
if (ql <= l && r <= qr) {
lazy[i] ^= 1;
upd(i);
return;
}
int m = (l + r) / 2;
update(i * 2, l, m, ql, qr);
update(i * 2 + 1, m + 1, r, ql, qr);
dp[i][0] = (dp[i * 2][0] + dp[i * 2 + 1][0]) % MOD;
dp[i][1] = (dp[i * 2][1] + dp[i * 2 + 1][1]) % MOD;
}
void build(int i, int l, int r) {
if (l == r) {
dp[i][A[l + N]] = exp(2, N - depth[l + N]);
return;
}
int m = (l + r) / 2;
build(i * 2, l, m);
build(i * 2 + 1, m + 1, r);
for (int k = 0; k < 2; ++k) {
dp[i][k] = (dp[i * 2][k] + dp[i * 2 + 1][k]) % MOD;
}
}
void init(int _N, int _M, std::vector<int> P, std::vector<int> _A) {
N = _N;
M = _M;
for (int i = N; i < N + M; ++i) {
A[i + 1] = _A[i - N];
}
for (int i = 1; i < N + M; ++i) {
adj[P[i] + 1].push_back(i + 1);
}
auto dfs = [&](auto& dfs, int i) -> void {
for (auto& u : adj[i]) {
depth[u] = depth[i] + 1;
dfs(dfs, u);
}
};
dfs(dfs, 1);
build(1, 1, M);
}
int count_ways(int L, int R) {
// cout << dp[1][1] << " -> ";
// cout << "[ " << L << " , " << R << " ]:\n";
L += 1;
R += 1;
update(1, 1, M, L - N, R - N);
// for (int i = 0; i < N + M; ++i) {
// cout << i << " = " << dp[i][0] << " " << dp[i][1] << "\n";
// }
// cout << "\n";
// for (int i = 0; i < N + M; ++i) {
// // update(0, 0, M - 1, i, i);
// cout << lazy[i] << " ";
// }
// cout << "\n";
return dp[1][1];
}
