#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array
#define vec vector
const int N = 1e5 + 5, M = 1e5 + 5, MD = 1000002022;
int n, m;
arr<vec<int>, N + M> ch;
arr<int, N + M> on;
int md(int x) { return (x + MD) % MD; }
arr<arr<int, 2>, N + M> dp;
arr<arr<int, 4>, N + M> kn;
void upd(int u) {
if (u >= n + 1) {
dp[u][0] = (on[u]) ? 0 : 1;
dp[u][1] = (on[u]) ? 1 : 0;
return;
}
int k = ch[u].size();
kn[0][0] = 1;
for (int i = 1; i <= k; i++) {
int v = ch[u][i - 1];
for (int c = 0; c <= k; c++) {
int lv = md(dp[v][0] * kn[i - 1][c]);
int tk = (c == 0) ? 0 : md(dp[v][1] * kn[i - 1][c - 1]);
kn[i][c] = md(lv + tk);
}
}
dp[u][0] = dp[u][1] = 0;
for (int c = 0; c <= k; c++) {
dp[u][0] = md(dp[u][0] + (k - c) * kn[k][c]);
dp[u][1] = md(dp[u][1] + c * kn[k][c]);
}
}
void init(sig _n, sig _m, vec<sig> _pr, vec<sig> _on) {
n = _n, m = _m;
for (int u = 2; u <= n + m; u++) {
int pr = _pr[u - 1] + 1;
ch[pr].push_back(u);
}
for (int u = n + 1; u <= n + m; u++)
on[u] = _on[u - n - 1];
for (int u = n + m; u >= 1; u--)
upd(u);
}
arr<bool, N + M> lzy;
void prp(int u) {
if (!lzy[u]) return;
for (int v : ch[u])
swap(dp[v][0], dp[v][1]), lzy[v] = true;
lzy[u] = true;
}
void dfs(int l, int r, int u = 1, int lw = n + 1, int hg = n + m) {
// cout << l << " " << r << ": " << lw << " " << hg << '\n';
if (l <= lw && hg <= r) {
swap(dp[u][0], dp[u][1]), lzy[u] = true;
return;
}
prp(u);
int md = (lw + hg) / 2;
if (l <= md) dfs(l, r, 2 * u, lw, md);
if (r > md) dfs(l, r, 2 * u + 1, md + 1, hg);
upd(u);
}
sig count_ways(sig l, sig r) {
l++, r++;
dfs(l, r);
return dp[1][1];
}
