#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
const int lim = 2e5 + 5;
const int mod = 1000002022;
void add(int& a, int b){
if((a += b) >= mod){
a -= mod;
}
}
int n, m, pw_2[lim], st[lim << 2], a[lim];
bitset<lim << 2>lazy;
void fix(int id, int l, int r, int m){
st[id] = (1LL * st[id << 1] * st[id << 1 | 1] + 1LL * st[id << 1] * (pw_2[r - m - 1] - st[id << 1 | 1] + mod) + 1LL * st[id << 1 | 1] * (pw_2[m - l] - st[id << 1] + mod)) % mod;
}
void flip(int id, int l, int r){
st[id] = (pw_2[r - l] - st[id] + mod) % mod;
lazy.flip(id);
}
void push_down(int id, int l, int r, int m){
if(lazy.test(id)){
lazy.reset(id);
flip(id << 1, l, m);
flip(id << 1 | 1, m + 1, r);
}
}
void build(int id, int l, int r){
if(l == r){
st[id] = int(a[l] == 1);
return;
}
int m = (l + r) >> 1;
build(id << 1, l, m);
build(id << 1 | 1, m + 1, r);
fix(id, l, r, m);
}
void update(int id, int l, int r, int u, int v){
if(l > v || r < u){
return;
}
if(u <= l && v >= r){
flip(id, l, r);
return;
}
int m = (l + r) >> 1;
push_down(id, l, r, m);
update(id << 1, l, m, u, v);
update(id << 1 | 1, m + 1, r, u, v);
fix(id, l, r, m);
}
void init(int N, int M, vector<int>P, vector<int>A){
n = N;
m = M;
for(int i = 0; i < m; i++){
a[i] = A[i];
}
for(int i = pw_2[0] = 1; i < lim; i++){
pw_2[i] = (pw_2[i - 1] << 1) % mod;
}
lazy.reset();
build(1, 0, m - 1);
}
int count_ways(int L, int R){
update(1, 0, m - 1, L, R);
return st[0];
}
