#include "circuit.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#define mod 1000002022ll
using namespace std;
struct SegmentTree {
#define m (l+r>>1)
#define lc (rt<<1)
#define rc (lc^1)
struct Node {long long sum, val; bool inv;};
int n;
vector<Node> st;
vector<long long> a;
SegmentTree(int _n, vector<long long> _a) : n(_n), st(n*4+4, {0, 0, 0}), a(_a) {
build(0, n-1, 1);
}
SegmentTree() {}
void build(int l, int r, int rt) {
if (l == r) return st[rt] = {a[l], 0, 0}, void();
build(l, m, lc);
build(m+1, r, rc);
st[rt].sum = (st[lc].sum + st[rc].sum) % mod;
}
void add_tag(int rt) {
st[rt].inv ^= 1;
st[rt].val = (st[rt].sum - st[rt].val + mod) % mod;
}
void push(int rt) {
if (st[rt].inv) {
add_tag(lc);
add_tag(rc);
st[rt].inv = 0;
}
}
void pull(int rt) {
st[rt].val = (st[lc].val + st[rc].val) % mod;
}
void modify(int ql, int qr) {modify(ql, qr, 0, n-1, 1);}
void modify(int ql, int qr, int l, int r, int rt) {
if (qr < l || r < ql) return;
if (ql <= l && r <= qr) return add_tag(rt), void();
push(rt);
modify(ql, qr, l, m, lc);
modify(ql, qr, m+1, r, rc);
pull(rt);
}
long long query_all() {
return st[1].val;
}
#undef m
#undef lc
#undef rc
};
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, opt;
SegmentTree st;
long long ans;
Tree (int _n) : n(_n), chd(_n), par(_n), dp(_n), sz(_n), we(_n), opt(_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 {
opt[u] = 1;
for (int v: chd[u]) {
par[v] = u;
dfs(dfs, v);
sz[u] += sz[v];
opt[u] = opt[u] * opt[v] % mod;
}
if (chd[u].size()) {
opt[u] = opt[u] * chd[u].size() % mod;
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]) {
long long o = 1;
for (int w: chd[u]) if (w != v) o = o * opt[w] % mod;
dfs2(dfs2, v, mul * o % mod);
}
};
dfs2(dfs2, 0, 1);
ans = dp[0];
// for (int i=0; i<n; i++) cout << we[i] << " "; cout << "\n";
st = SegmentTree(n, we);
}
long long toggle(int l, int r) {
st.modify(l, r);
return st.query_all();
}
};
Tree t;
int count_ways(int L, int R) {
return t.toggle(L, R);
}
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);
}
t.init();
for (int i=n; i<n+m; i++) {
if (a[i-n]) t.toggle(i, i);
}
}
