#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define rall(s) s.rbegin(), s.rend()
#define all(s) s.begin(), s.end()
#define sz(s) (int) s.size()
#define s second
#define f first
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int N = 1e6, mod = 1000002022;
int n, m, is = 1;
vector<int> g[N], a(N);
vector<ll> pr(N), sf(N), val(N), gvl(N);
void calc(int u) {
for (int to: g[u]) {
calc(to);
}
int M = sz(g[u]);
if (!M) {
val[u] = 1;
return;
}
for (int i = 0; i < M; i++) {
if (i) pr[i] = pr[i - 1];
else pr[i] = 1;
pr[i] = (pr[i] * val[g[u][i]]) % mod;
}
for (int i = M - 1; i >= 0; i--) {
if (i < M - 1) sf[i] = sf[i + 1];
else sf[i] = 1;
sf[i] = (sf[i] * val[g[u][i]]) % mod;
}
for (int i = 0; i < M; i++) {
gvl[g[u][i]] = ((i ? pr[i - 1] : 1ll) * (i < M - 1 ? sf[i + 1] : 1ll)) % mod;
}
val[u] = (pr[M - 1] * M) % mod;
}
ll vl[N];
void dfs(int u, int x) {
int M = sz(g[u]);
if (!M) {
vl[u - n] = x;
return;
}
for (int to: g[u]) {
dfs(to, (x * gvl[to]) % mod);
}
}
pll t[4 * N];
int swp[4 * N];
void bld(int u = 1, int tl = 0, int tr = m - 1) {
if (tl == tr) {
if (a[tl]) t[u].f = vl[tl];
else t[u].s = vl[tl];
return;
}
int mid = (tl + tr) / 2;
bld(u * 2, tl, mid);
bld(u * 2 + 1, mid + 1, tr);
t[u].f = (t[u * 2].f + t[u * 2 + 1].f) % mod;
t[u].s = (t[u * 2].s + t[u * 2 + 1].s) % mod;
}
void push(int u, int tl, int tr) {
if (!swp[u]) return;
swap(t[u].f, t[u].s);
if (tl < tr) {
swp[u * 2] ^= 1;
swp[u * 2 + 1] ^= 1;
}
swp[u] = 0;
}
void upd(int l, int r, int u = 1, int tl = 0, int tr = m - 1) {
push(u, tl, tr);
if (tl > r || tr < l) return;
if (tl >= l && tr <= r) {
swp[u] = 1;
push(u, tl, tr);
return;
}
int mid = (tl + tr) / 2;
upd(l, r, u * 2, tl, mid);
upd(l, r, u * 2 + 1, mid + 1, tr);
t[u].f = (t[u * 2].f + t[u * 2 + 1].f) % mod;
t[u].s = (t[u * 2].s + t[u * 2 + 1].s) % mod;
}
void init(int nn, int M, vector<int> P, vector<int> A) {
n = nn, m = M;
for (int i = 0; i < m; i++) a[i] = A[i];
for (int i = 1; i < n + m; i++) g[P[i]].push_back(i);
calc(0), dfs(0, 1), bld();
}
int count_ways(int l, int r) {
upd(l - n, r - n);
return t[1].f;
}
