#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1000002022;
vector<vector<int>> v;
vector<vector<ll>> d;
vector<vector<ll>> d2;
vector<int> A, pr, psh;
int N, M;
void build(int x, int tl, int tr) {
if (tl == tr) {
d[x][A[tl - N]] = 1;
d[x][A[tl - N] ^ 1] = 0;
d2[x][A[tl - N]] = 0;
d2[x][A[tl - N] ^ 1] = 1;
// cout << x << " " << d[x][A[tl - N]] << " " << d2[x][A[tl - N] ^ 1] << "\n";
return;
}
int lft = 2 * x + 1, rgh = 2 * x + 2;
int tm = (tl + tr) / 2;
build(lft, tl, tm);
build(rgh, tm + 1, tr);
d[x][0] = ((((d[lft][0] * d[rgh][0]) % MOD) * 2 % MOD) +
(d[lft][1] * d[rgh][0] % MOD + d[lft][0] * d[rgh][1] % MOD) % MOD) % MOD;
d[x][1] = ((d[lft][1] * d[rgh][0] % MOD + d[lft][0] * d[rgh][1] % MOD) % MOD
+ (d[lft][1] * d[rgh][1] % MOD) * 2 % MOD) % MOD;
d2[x][0] = (((d2[lft][0] * d2[rgh][0]) % MOD) * 2 % MOD +
(d2[lft][1] * d2[rgh][0] % MOD + d2[lft][0] * d2[rgh][1] % MOD) % MOD) % MOD;
d2[x][1] = ((d2[lft][1] * d2[rgh][0] % MOD + d2[lft][0] * d2[rgh][1] % MOD) % MOD
+ (d2[lft][1] * d2[rgh][1] % MOD) * 2 % MOD) % MOD;
}
void upd(int x, int tl, int tr, int L, int R) {
if (R < tl || L > tr)
return;
if (L <= tl && R >= tr) {
psh[x] ^= 1;
swap(d[x][0], d2[x][0]);
swap(d[x][1], d2[x][1]);
return;
}
int lft = 2 * x + 1, rgh = 2 * x + 2;
if (psh[x]) {
psh[x] = 0;
psh[lft] ^= 1;
psh[rgh] ^= 1;
swap(d[lft][0], d2[lft][0]);
swap(d[lft][1], d2[lft][1]);
swap(d[rgh][0], d2[rgh][0]);
swap(d[rgh][1], d2[rgh][1]);
}
int tm = (tl + tr) / 2;
upd(lft, tl, tm, L, R);
upd(rgh, tm + 1, tr, L, R);
d[x][0] = ((((d[lft][0] * d[rgh][0]) % MOD) * 2 % MOD) +
(d[lft][1] * d[rgh][0] % MOD + d[lft][0] * d[rgh][1] % MOD) % MOD) % MOD;
d[x][1] = ((d[lft][1] * d[rgh][0] % MOD + d[lft][0] * d[rgh][1] % MOD) % MOD
+ (d[lft][1] * d[rgh][1] % MOD) * 2 % MOD) % MOD;
d2[x][0] = (((d2[lft][0] * d2[rgh][0]) % MOD) * 2 % MOD +
(d2[lft][1] * d2[rgh][0] % MOD + d2[lft][0] * d2[rgh][1] % MOD) % MOD) % MOD;
d2[x][1] = ((d2[lft][1] * d2[rgh][0] % MOD + d2[lft][0] * d2[rgh][1] % MOD) % MOD
+ (d2[lft][1] * d2[rgh][1] % MOD) * 2 % MOD) % MOD;
}
void init(int N, int M, vector<int> P, vector<int> A) {
pr.resize(N + M);
v.resize(N + M);
d.resize(N + M);
d2.resize(N + M);
psh.resize(N + M);
::A = A;
::N = N;
::M = M;
for (int i = 0; i < N + M; i++) {
d[i].resize(2);
d2[i].resize(2);
psh[i] = 0;
}
build(0, N, N + M - 1);
}
int count_ways(int L, int R) {
upd(0, N, N + M - 1, L, R);
return d[0][1];
}
