#include "circuit.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz size()
#define F first
#define S second
vector<int> a;
ll siz = 1;
pair<ll,ll> seg[2*200005];
ll n;
ll mod = 1000002022;
ll op[2*200005];
void build(ll x = 0, ll lx = 0, ll rx = siz)
{
if(rx-lx==1)
{
seg[x].F = a[lx];
seg[x].S = !a[lx];
return;
}
ll mid = (lx+rx)/2;
build(2*x+1,lx,mid);
build(2*x+2,mid,rx);
seg[x].F = 2*seg[2*x+1].F*seg[2*x+2].F + seg[2*x+1].S*seg[2*x+2].F + seg[2*x+1].F*seg[2*x+2].S;
seg[x].S = 2*seg[2*x+1].S*seg[2*x+2].S + seg[2*x+1].S*seg[2*x+2].F + seg[2*x+1].F*seg[2*x+2].S;
seg[x].F %= mod;
seg[x].S %=mod;
}
void upd(ll l , ll r, ll x = 0, ll lx = 0, ll rx = siz)
{
if(lx>=r||rx<=l) return;
if(lx>=l&&rx<=r)
{
swap(seg[x].F, seg[x].S);
op[x] ^= 1;
return;
}
ll mid = (lx+rx)/2;
upd(l,r,2*x+1,lx,mid);
upd(l,r,2*x+2,mid,rx);
seg[x].F = 2*seg[2*x+1].F*seg[2*x+2].F + seg[2*x+1].S*seg[2*x+2].F + seg[2*x+1].F*seg[2*x+2].S;
seg[x].S = 2*seg[2*x+1].S*seg[2*x+2].S + seg[2*x+1].S*seg[2*x+2].F + seg[2*x+1].F*seg[2*x+2].S;
if(op[x]) swap(seg[x].F, seg[x].S);
seg[x].F %= mod;
seg[x].S %=mod;
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
siz = M;
a = A;
n = N;
build();
}
int count_ways(int L, int R) {
upd(L,R+1);
return seg[0].F;
return 0;
}
