#include "circuit.h"
#include <bits/stdc++.h>
#define maxn 100005
#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 dp[maxn+maxn][2], c[maxn+maxn], lz[maxn+maxn];
void pfs(int u) {
if (u >= n) {
c[u] = 0;
return;
}
for (int v : adj[u]) {
pfs(v);
if (v < n) c[u] = 1LL * c[u] * c[v] % mod;
}
c[u] = 1LL * c[u] * int(adj[u].size()) % mod;
}
void pfsTwo(int u) {
if (u >= n) {
dp[u][a[u-n+1]] = 1;
dp[u][1-a[u-n+1]] = 0;
return;
}
int L = (u<<1)+1, R = (u<<1|1)+1;
pfsTwo(L);
pfsTwo(R);
dp[u][0] = (2LL * dp[L][0] * dp[R][0] + 1LL * dp[L][1] * dp[R][0] + 1LL * dp[L][0] * dp[R][1]) % mod;
dp[u][1] = (2LL * dp[L][1] * dp[R][1] + 1LL * dp[L][1] * dp[R][0] + 1LL * dp[L][0] * dp[R][1]) % mod;
}
void apply(int r) {
swap(dp[r][0], dp[r][1]);
lz[r] ^= 1;
}
void down(int r) {
if (lz[r]) {
apply((r<<1)+1);
apply((r<<1|1)+1);
lz[r] = 0;
}
}
void up(int v) {
int L = (v<<1)+1, R = (v<<1|1)+1;
dp[v][0] = (2LL * dp[L][0] * dp[R][0] + 1LL * dp[L][1] * dp[R][0] + 1LL * dp[L][0] * dp[R][1]) % mod;
dp[v][1] = (2LL * dp[L][1] * dp[R][1] + 1LL * dp[L][1] * dp[R][0] + 1LL * dp[L][0] * dp[R][1]) % mod;
}
void update(int u, int v, int r = 0, 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)+1, lo, mid);
if (v > mid) update(u, v, (r<<1|1)+1, mid+1, hi);
up(r);
}
//3, 4
//3, 6
//3->4, 5->6
//3->3, 4->4, 5->5, 6->6
void init(int N, int M, vector<int> P, vector<int> A) {
for (int i = 1; i < N+M; i++) adj[P[i]].emplace_back(i);
for (int i = 0; i < M; i++) a[i+1] = A[i];
n = N;
m = M;
pfs(0);
pfsTwo(0);
}
int count_ways(int L, int R) {
update(L, R);
return dp[0][1];
}
