#include "circuit.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#define mod 1000002022ll
using namespace std;
// dp[u] = (2^(sz[u]-1) - (2^sz[v] - dp[v]) * (2^sz[w] - dp[w])) + dp[v] * dp[w]
// dp[u] =
long long p2[(int)5e5];
int n, m;
vector<int> a;
struct Tree {
int n;
vector<vector<int>> chd;
vector<int> par;
vector<long long> dp, sz;
Tree (int _n) : n(_n), chd(_n), par(_n), dp(_n), sz(_n) {}
Tree () {}
void pull(int u) {
int v = chd[u][0], w = chd[u][1];
dp[u] = (p2[sz[v]] * dp[w] + p2[sz[w]] * dp[v]) % mod;
}
void init() {
auto dfs = [&] (auto dfs, int u) -> void {
for (int v: chd[u]) {
par[v] = u;
dfs(dfs, v);
sz[u] += sz[v];
}
if (chd[u].size()) {
sz[u]++;
pull(u);
}
};
dfs(dfs, 0);
}
long long toggle(int u) {
// for (int i=0; i<n; i++) cout << dp[i] << " "; cout << " dp\n";
dp[u] ^= 1;
while (u != 0) {
pull(par[u]);
u = par[u];
}
return dp[0];
}
};
Tree t;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
p2[0] = 1;
for (int i=1; i<5e5; i++) p2[i] = p2[i-1] * 2 % mod;
n = N;
m = M;
a = A;
t = Tree(n + m);
for (int i=1; i<n+m; i++) {
t.chd[P[i]].push_back(i);
}
for (int i=n; i<n+m; i++) {
t.dp[i] = a[i-n];
}
t.init();
}
int count_ways(int L, int R) {
return t.toggle(L);
}
