#include "circuit.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const int K=1<<18;
const ll mod=1e9+2022;
int n,m;
int a[N];
ll pw[N];
ll mul;
struct segtree{
int t[K];
bool lz[K];
void pushlz(int l,int r,int i){
if(!lz[i])return;
t[i]=r-l+1-t[i];
if(l<r){
lz[i*2]^=true;
lz[i*2+1]^=true;
}
lz[i]=false;
}
void build(int l,int r,int i){
if(l==r)return void(t[i]=a[l]);
int m=(l+r)/2;
build(l,m,i*2);
build(m+1,r,i*2+1);
t[i]=t[i*2]+t[i*2+1];
}
void build(){
build(1,m,1);
}
void update(int l,int r,int i,int x,int y){
pushlz(l,r,i);
if(y<l||r<x)return;
if(x<=l&&r<=y)return lz[i]=true,pushlz(l,r,i),void();
int m=(l+r)/2;
update(l,m,i*2,x,y);
update(m+1,r,i*2+1,x,y);
t[i]=t[i*2]+t[i*2+1];
}
void update(int x,int y){
update(1,m,1,x,y);
}
}s;
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n=N,m=M;
pw[0]=1;
for(int i=1;i<=n;i++)pw[i]=pw[i-1]*2%mod;
for(int i=1;i<=m;i++)a[i]=A[i-1];
s.build();
int cur=1;
mul=1;
while(cur<n){
mul*=pw[cur];
mul%=mod;
cur=cur*2+1;
}
}
int count_ways(int L, int R) {
L-=n-1;
R-=n-1;
s.update(L,R);
return (mul*s.t[1])%mod;
}
