#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000002022;
const int MAXN = 2e5 + 5;
int A[MAXN + 1];
int N, M;
int cnt1[MAXN], cnth[MAXN], cnt0[MAXN];
ll M2;
void update(int i, int l, int r, int ql, int qr, bool add = false) {
// cout << l << " " << r << " " << ql << " " << qr << "\n";
if (ql > r || l > qr) return;
if (ql <= l && r <= qr) {
int tmp = cnt0[i];
cnt0[i] = cnt1[i];
cnt1[i] = tmp;
if (add) {
// cout << l << " " << r << " = " << A[l] << "\n";
if (A[l]) cnt1[i] += 1;
else cnt0[i] += 1;
}
return;
}
int m = (l + r) / 2;
update(i * 2, l, m, ql, qr, add);
update(i * 2 + 1, m + 1, r, ql, qr, add);
cnt0[i] = cnt0[i * 2] + cnt0[i * 2 + 1];
cnt1[i] = cnt1[i * 2] + cnt1[i * 2 + 1];
}
void init(int _N, int _M, std::vector<int> P, std::vector<int> _A) {
N = _N;
M = _M;
for (int i = N; i < N + M; ++i) {
A[i + 1] = _A[i - N];
update(1, 1, N + M, i + 1, i + 1, true);
}
M2 = (M / 2) * M % MOD;
// cout << cnt1[1] << "\n";
}
int count_ways(int L, int R) {
L += 1;
R += 1;
update(1, 1, N + M, L, R);
ll tot = cnt1[1];
return (tot * M % MOD * M2) % MOD;
}
