#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#include "circuit.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MOD = 1'000'002'022;
const int MAXN = 100'055;
inline void add(int &a, int b) { a += b; if(MOD <= a) a -= MOD; }
inline void sub(int &a, int b) { a -= b; if(a < 0) a += MOD; }
struct SEG {
int d[MAXN*4][2];
bitset<MAXN*4> df;
vector<int> *Q;
int *A;
void init(int i, int s, int e) {
if(s == e) {
d[i][(*Q)[s]] = A[s];
return;
}
int m = s+e >> 1;
init(i<<1, s, m);
init(i<<1|1, m+1, e);
for(int j = 2; j--;) {
d[i][j] = d[i<<1][j];
add(d[i][j], d[i<<1|1][j]);
}
}
pii f(int i, int s, int e, int p, int q) {
if(q < s || e < p) return {0, 0};
if(p <= s && e <= q) {
swap(d[i][0], d[i][1]);
df[i] = !df[i];
return {d[i][1], d[i][0]};
}
int m = s+e >> 1;
pii r = f(i<<1, s, m, p, q);
pii t = f(i<<1|1, m+1, e, p, q);
add(r.fi, t.fi); add(r.se, t.se);
for(int j = 2; j--;) {
d[i][j] = d[i<<1][j];
add(d[i][j], d[i<<1|1][j]);
}
if(df[i]) {
swap(d[i][0], d[i][1]);
swap(r.fi, r.se);
}
return r;
}
} seg;
vector<int> G[MAXN*2];
int A[MAXN*2], B[MAXN*2];
int N, M, Ans;
void dfs1(int i) {
int r = max(1, sz(G[i]));
for(int v : G[i]) {
dfs1(v);
r = ll(r) * B[v] % MOD;
}
B[i] = r;
}
void dfs2(int i) {
int u = A[i];
int dg = sz(G[i]);
vector<int> L(dg, 1), R(dg, 1);
for(int j = 1; j < dg; j++)
L[j] = ll(L[j-1]) * B[G[i][j-1]] % MOD;
for(int j = dg-2; 0 <= j; j--)
R[j] = ll(R[j+1]) * B[G[i][j+1]] % MOD;
for(int j = dg; j--;) {
int v = G[i][j];
A[v] = ll(u) * L[j] % MOD * R[j] % MOD;
dfs2(v);
}
}
void init(int N, int M, std::vector<int> P, std::vector<int> Q) {
::N = N; ::M = M;
for(int i = N+M; --i;) G[P[i]].eb(i);
dfs1(0); A[0] = 1; dfs2(0);
for(int i = 0; i < M; i++) A[i] = A[N+i];
seg.A = A; seg.Q = &Q;
seg.init(1, 0, M-1);
B[0] = 0;
for(int i = 1; i <= M; i++) {
B[i] = B[i-1];
add(B[i], A[i-1]);
}
for(int i = M; i--;) if(Q[i]) add(Ans, A[i]);
}
int count_ways(int L, int R) {
L -= N; R -= N;
int r = seg.f(1, 0, M-1, L, R).se;
add(Ans, B[R+1]); sub(Ans, B[L]);
add(r, r); sub(Ans, r);
return Ans;
}
