#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
vector<int> p;
vector<int> a;
vector<vector<int>> adj;
vector<int> h;
int n, m;
const ll MOD = 1000002022;
const int mxN = 200000+5;
ll pw[mxN];
void ordfs(int u) {
if (adj[u].size()==0) return;
int l = adj[u][0];
int r = adj[u][1];
h[l] = h[u]+1;
h[r] = h[u]+1;
ordfs(l);
ordfs(r);
}
struct SegTree {
ll tree[4*mxN][2];
int lazy[4*mxN];
SegTree() {
memset(tree, 0, sizeof(tree));
memset(lazy, 0, sizeof(lazy));
}
void query(int u, int l, int r, int i) {
if (l>i || r<i) {
return;
}
if (l==r) {
tree[u][a[i]] = pw[n-h[i+n]];
tree[u][1-a[i]] = 0;
}
else {
int m = (l+r)/2;
query(2*u, l, m, i);
query(2*u+1, m+1, r, i);
tree[u][0] = tree[2*u][0] + tree[2*u+1][0];
tree[u][1] = tree[2*u][1] + tree[2*u+1][1];
tree[u][0] %= MOD;
tree[u][1] %= MOD;
}
}
void prop(int u, int l, int r) {
if (lazy[u]&1) {
swap(tree[u][0], tree[u][1]);
}
if (l!=r) {
lazy[2*u] += lazy[u];
lazy[2*u+1] += lazy[u];
lazy[2*u] %= 2;
lazy[2*u+1] %= 2;
}
lazy[u] = 0;
}
void update(int u, int l, int r, int i, int j) {
prop(u, l, r);
if (l>j || r<i) return;
if (i<=l && r<=j) {
lazy[u] += 1;
lazy[u] %= 2;
prop(u, l, r);
return;
}
int m = (l+r)/2;
update(2*u, l, m, i, j);
update(2*u+1, m+1, r, i, j);
//cout << tree[u][0] << " " << tree[u][1] << "\n";
tree[u][0] = tree[2*u][0] + tree[2*u+1][0];
tree[u][1] = tree[2*u][1] + tree[2*u+1][1];
//cout << tree[u][0] << " " << tree[u][1] << "\n";
tree[u][0] %= MOD;
tree[u][1] %= MOD;
}
};
SegTree st;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
st = SegTree();
h.assign(mxN, 0);
h[0] = 0;
p = P;
n = N, m = M;
adj.assign(n+m, {});
for (int i=1; i<n+m; i++) {
adj[P[i]].push_back(i);
}
a = A;
ordfs(0);
pw[0] = 1;
for (int i=1; i<mxN; i++) {
pw[i] = pw[i-1]*2;
pw[i] %= MOD;
}
for (int i=n; i<n+m; i++) {
//cout << a[i-n] << endl;
st.query(1, 0, m-1, i-n);
}
}
int count_ways(int L, int R) {
L -= n;
R -= n;
st.update(1, 0, m-1, L, R);
return st.tree[1][1];
}
