#include "circuit.h"
#include <bits/stdc++.h>
#define maxn 200005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
constexpr int mod = 1'000'002'022;
inline constexpr void add(int &x, const int &y) {x += y; if (x >= mod) x -= mod;}
int a[maxn], n, m;
vector<int> adj[maxn];
int s[maxn], contribution[maxn];
void pfsOne(int u) {
s[u] = 1;
for (int v : adj[u]) {
pfsOne(v);
s[u] = 1LL * s[u] * s[v] % mod;
}
if (u < n) s[u] = 1LL * s[u] * int(adj[u].size()) % mod;
}
void pfsTwo(int u) {
int S = (u == 0 ? 1 : contribution[u]);
for (int v : adj[u]) {
contribution[v] = S;
S = 1LL * S * s[v] % mod;
}
reverse(adj[u].begin(), adj[u].end());
S = 1;
for (int v : adj[u]) {
contribution[v] = 1LL * contribution[v] * S % mod;
S = 1LL * S * s[v] % mod;
}
for (int v : adj[u]) {
pfsTwo(v);
}
}
int sum[4*maxn], st[4*maxn], lz[4*maxn];
void apply(int r) {
st[r] = (sum[r] - st[r] + mod) % mod;
lz[r] ^= 1;
}
void down(int r) {
if (lz[r]) {
apply(r<<1);
apply(r<<1|1);
lz[r] = 0;
}
}
void up(int r) {
st[r] = (st[r<<1] + st[r<<1|1]) % mod;
}
void build(int r = 1, int lo = n, int hi = n+m-1) {
if (lo == hi) {
sum[r] = contribution[lo];
st[r] = contribution[lo] * a[lo-n];
return;
}
int mid = (lo + hi) >> 1;
build(r<<1, lo, mid);
build(r<<1|1, mid+1, hi);
sum[r] = (sum[r<<1] + sum[r<<1|1]) % mod;
st[r] = (st[r<<1] + st[r<<1|1]) % mod;
}
void update(int u, int v, int r = 1, int lo = n, int hi = n+m-1) {
if (u <= lo && hi <= v) {
apply(r);
return;
}
down(r);
int mid = (lo + hi) >> 1;
if (u <= mid) update(u, v, r<<1, lo, mid);
if (v > mid) update(u, v, r<<1|1, mid+1, hi);
up(r);
}
void init(int N, int M, vector<int> P, vector<int> A) {
n = N; m = M;
for (int i = 1; i < N+M; i++) adj[P[i]].emplace_back(i);
for (int i = 0; i < M; i++) a[i] = A[i];
pfsOne(0); pfsTwo(0);
build();
}
int count_ways(int L, int R) {
update(L, R);
return st[1];
}
