#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sep ' '
#define debug(x) cerr << #x << ": " << x << endl;
const ll MOD = 1000002022;
const ll MAXN = 1e6 + 10;
ll Z[MAXN], n, m, A[MAXN], CZ[MAXN], pw2;
vector<int> adj[MAXN];
namespace segment {
ll sg[MAXN][2], lz[MAXN];
void build(int l = 0, int r = m - 1, int v = 1) {
if (l == r) sg[v][1 - A[l]] = Z[l];
else {
int mid = (l + r) >> 1;
build(l, mid, v << 1);
build(mid + 1, r, v << 1 | 1);
sg[v][0] = (sg[v << 1][0] + sg[v << 1 | 1][0]) % MOD;
sg[v][1] = (sg[v << 1][1] + sg[v << 1 | 1][1]) % MOD;
}
}
void push(int v) {
if (lz[v]) {
swap(sg[v][0], sg[v][1]);
if ((v << 1 | 1) < MAXN) lz[v << 1] ^= 1, lz[v << 1 | 1] ^= 1;
lz[v] = 0;
}
}
void update(int ql, int qr, int l = 0, int r = m - 1, int v = 1) {
push(v);
if (ql > r || qr < l) return;
if (ql <= l && qr >= r) {
lz[v] ^= 1;
push(v);
return;
}
int mid = (l + r) >> 1;
update(ql, qr, l, mid, v << 1);
update(ql, qr, mid + 1, r, v << 1 | 1);
sg[v][0] = (sg[v << 1][0] + sg[v << 1 | 1][0]) % MOD;
sg[v][1] = (sg[v << 1][1] + sg[v << 1 | 1][1]) % MOD;
}
}
void dfs0(int v) {
CZ[v] = (v < n ? adj[v].size() : 1);
for (int u : adj[v]) {
dfs0(u);
CZ[v] = CZ[v] * CZ[u] % MOD;
}
}
void dfs1(int v, ll z) {
if (v >= n) {
Z[v - n] = z;
return;
}
int d = adj[v].size();
vector<ll> pref_z(d + 2), suff_z(d + 2);
pref_z[0] = 1;
suff_z[d + 1] = 1;
for (int i = 1; i <= d; i++)
pref_z[i] = pref_z[i - 1] * CZ[adj[v][i - 1]] % MOD;
for (int i = d; i > 0; i--)
suff_z[i] = suff_z[i + 1] * CZ[adj[v][i - 1]] % MOD;
for (int i = 1; i <= d; i++) {
dfs1(adj[v][i - 1], z * pref_z[i - 1] % MOD * suff_z[i + 1] % MOD);
}
}
void init(int N_, int M_, vector<int> P, vector<int> A_) {
n = N_, m = M_;
for (int i = 0; i < m; i++)
A[i] = A_[i];
for (int i = 1; i < n + m; i++)
adj[P[i]].push_back(i);
dfs0(0);
dfs1(0, 1);
segment::build();
pw2 = 1;
for (int i = 0; i < m; i++)
pw2 = pw2 * 2 % MOD;
}
int count_ways(int L, int R) {
L -= n, R -= n;
segment::update(L, R);
return segment::sg[1][0] % MOD;
}
