#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
const int MOD = 1000002022;
const int LOG = 26;
vector<int> ans;
struct light {
long long on, off;
};
light merge(light a, light b) {
light res;
res.on = (((a.on * b.off) % MOD + (a.off * b.on) % MOD) % MOD + (2*a.on * b.on) % MOD) %MOD;
res.off = (((a.off * b.on) % MOD + (a.on * b.off) % MOD) % MOD + (2*a.off * b.off) % MOD) %MOD;
return res;
}
struct segTree {
vector<light> t;
vector<bool> lazy;
void propagate(int i, int l, int r) {
if (!lazy[i]) return;
swap(t[i].on, t[i].off);
if (l != r) {
lazy[2*i] = !lazy[2*i];
lazy[2*i+1] = !lazy[2*i+1];
}
lazy[i] = false;
}
void init(int sz) {
t.resize(4*sz);
lazy.resize(4*sz, false);
}
void updt(int i) {
t[i] = merge(t[i*2], t[i*2+1]);
}
void build(int i, int l, int r, vector<int> &v) {
if (l==r) {
if (v[l]) {
t[i].on = 1;
t[i].off = 0;
} else {
t[i].off = 1;
t[i].on = 0;
}
return;
}
int mid = (l+r)/2;
build(2*i, l, mid, v);
build(2*i+1, mid+1, r, v);
updt(i);
}
void update(int i, int l, int r, int qL, int qR) {
propagate(i, l, r);
if (qR < l || qL > r) return;
if (qL <= l && qR >= r) {
//cerr << i << ' ';
//cerr << t[i].off << ' ';
lazy[i] = true;
propagate(i, l, r);
//cerr << t[i].on << ' ';
return;
}
int mid = (l+r)/2;
update(2*i, l, mid, qL, qR);
update(2*i+1, mid+1, r, qL, qR);
updt(i);
//cerr << t[i].on << ' ';
}
};
int m, n;
segTree seg;
void init(int N, int M, vector<int> P, vector<int> A) {
m = M; n = N;
seg.init(M);
seg.build(1, 0, M-1, A);
}
int count_ways(int L, int R) {
seg.update(1, 0, m-1, L-n, R-n);
return(seg.t[1].on);
}
