#include "circuit.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#define mod 1000002022ll
using namespace std;
struct SegmentTree {
struct Node {long long sum, val; bool inv;};
int n;
vector<Node> st;
SegmentTree(int _n) : n(_n), st() {}
};
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, we;
long long ans;
Tree (int _n) : n(_n), chd(_n), par(_n), dp(_n), sz(_n), we(_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;
sz[u] += sz[v];
}
if (chd[u].size()) {
sz[u]++;
pull(u);
}
};
dfs(dfs, 0);
auto dfs2 = [&] (auto dfs2, int u, long long mul) -> void {
if (chd[u].size() == 0) we[u] = mul;
for (int v: chd[u]) {
dfs2(dfs2, v, mul * p2[sz[u] - sz[v] - 1] % mod);
}
};
dfs2(dfs2, 0, 1);
ans = dp[0];
}
long long toggle(int u) {
dp[u] ? ans -= we[u] : ans += we[u];
dp[u] ^= 1;
return ans;
}
};
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);
}
