#include "circuit.h"
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define ff first
#define ss second
const int mod = 1'000'002'022;
struct lazy {
struct node {
ll one, zero;
bool lazy;
node() {
one = zero = 0;
lazy = false;
}
void merge(const node &a, const node &b) {
one = (a.one * b.one * 2 + a.one * b.zero + a.zero * b.one) % mod;
zero = (a.zero * b.zero * 2 + a.one * b.zero + a.zero * b.one) % mod;
}
void impact() {
swap(one, zero);
lazy = !lazy;
}
void propagate(node &a, node &b) {
if (lazy) {
a.impact();
b.impact();
lazy = false;
}
}
};
vector<node> tree;
int size;
node neutral_element;
void build(const vector<int> &a) {
size = 1;
while (size < a.size()) size *= 2;
tree.assign(2 * size - 1, neutral_element);
for (int i = size - 1; i < size - 1 + a.size(); i++) {
if (a[i - size + 1]) tree[i].one = 1;
else tree[i].zero = 1;
}
for (int i = size - 2; i >= 0; i--) {
tree[i].merge(tree[i * 2 + 1], tree[i * 2 + 2]);
// cout << i << ' ' << tree[i].one << ' ' << tree[i].zero << endl;
}
}
void upd(int l, int r, int x, int lx, int rx) {
if (lx >= r or l >= rx) return;
if (l <= lx and rx <= r) {
tree[x].impact();
return;
}
tree[x].propagate(tree[2 * x + 1], tree[2 * x + 2]);
int mid = (lx + rx) >> 1;
upd(l, r, 2 * x + 1, lx, mid);
upd(l, r, 2 * x + 2, mid, rx);
tree[x].merge(tree[2 * x + 1], tree[2 * x + 2]);
}
void upd(int l, int r) {
upd(l, r + 1, 0, 0, size);
}
node get(int l, int r, int x, int lx, int rx) {
if (lx >= r or l >= rx) return neutral_element;
if (l <= lx and rx <= r) return tree[x];
tree[x].propagate(tree[2 * x + 1], tree[2 * x + 2]);
int mid = (lx + rx) >> 1;
node ans;
ans.merge(get(l, r, 2 * x + 1, lx, mid), get(l, r, 2 * x + 2, mid, rx));
return ans;
}
int get(int l, int r) {
return get(l, r + 1, 0, 0, size).one;
}
};
void upd(ll &a, ll b) {
a = (a + b) % mod;
if (a < 0) a += mod;
}
int n, m;
vector<int> a, p;
lazy sg;
void init(int _n, int _m, std::vector<int> P, std::vector<int> A) {
n = _n, m = _m;
a = A; p = P;
sg.build(a);
// cout << '\t' << sg.get(0, m - 1) << endl;
}
int count_ways(int L, int R) {
sg.upd(L - n, R - n);
return sg.get(0, m - 1);
}
