#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define x first
#define y second
#define pb push_back
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define all(a) a.begin(),a.end()
const int mod = 1000002022;
const int mx_m = 1e5;
int n,m;
vi a;
struct node{
int cnt0=0, cnt1=0;
bool flag=0;
node(int cnt0=0, int cnt1=0):cnt0(cnt0), cnt1(cnt1){}
};
node seg[4*mx_m];
void set_(int ind){
swap(seg[ind].cnt0, seg[ind].cnt1);
seg[ind].flag = !seg[ind].flag;
}
void push(int ind){
if(seg[ind].flag){
set_(2*ind);
set_(2*ind+1);
seg[ind].flag=0;
}
}
void pull(int ind){
seg[ind].cnt1 = ((seg[2*ind].cnt0 * seg[2*ind+1].cnt1) + (seg[2*ind].cnt1 * seg[2*ind+1].cnt0) + (2*seg[2*ind].cnt1*seg[2*ind+1].cnt1))%mod;
seg[ind].cnt0 = ((seg[2*ind].cnt0 * seg[2*ind+1].cnt1) + (seg[2*ind].cnt1 * seg[2*ind+1].cnt0) + (2*seg[2*ind].cnt0*seg[2*ind+1].cnt0))%mod;
}
void build(int ind, int l, int r){
if(l+1==r){
int cnt0 = 0, cnt1=1;
if(!a[l]) swap(cnt0, cnt1);
seg[ind] = node(cnt0, cnt1);
return;
}
int mid = (l+r)/2;
build(2*ind, l, mid);
build(2*ind+1, mid, r);
pull(ind);
}
void update_swap(int ind, int l, int r, int a, int b){
if(a<=l && r<=b){
set_(ind);
return;
}
if(l>=b || r<=a) return;
int mid = (l+r)/2;
push(ind);
update_swap(2*ind, l, mid, a,b);
update_swap(2*ind+1, mid, r, a,b);
pull(ind);
}
int query(){
return seg[1].cnt1;
}
void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
n=N;m=M;
a.resize(m);
loop(i,0,m){
a[i] = A[i];
}
build(1,0,m);
}
int32_t count_ways(int32_t L, int32_t R) {
int l=L, r=R;
l-=n; r-=n;
update_swap(1,0,m,l,r+1);
return query();
}
