#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int nax=4e5+5;
const int MOD = 1e9 + 2022 ;
int a[nax];
long long dp[2][nax];
bool lazy[nax];
int n,m;
void merge(int pos){
dp[0][pos]=dp[0][pos*2+1]*dp[1][pos*2+2]+dp[1][pos*2+1]*dp[0][pos*2+2]+dp[0][pos*2+1]*dp[0][pos*2+2]*2;
dp[1][pos]=dp[0][pos*2+1]*dp[1][pos*2+2]+dp[1][pos*2+1]*dp[0][pos*2+2]+dp[1][pos*2+1]*dp[1][pos*2+2]*2;
dp[0][pos]%=MOD;
dp[1][pos]%=MOD;
}
void build(int pos,int l,int r){
if(l==r){
dp[a[l]][pos]=1;
return;
}
int mid=(r+l)/2;
build(pos*2+1,l,mid);
build(pos*2+2,mid+1,r);
merge(pos);
}
void expand(int pos){
if(lazy[pos]){
swap(dp[0][pos*2+1],dp[1][pos*2+1]);
swap(dp[1][pos*2+1],dp[1][pos*2+2]);
}
lazy[pos]=0;
}
void update(int pos,int l,int r,int left,int right){
if(l>r||r<left||l>right) return;
if(left<=l&&r<=right){
lazy[pos]=1;
swap(dp[0][pos],dp[1][pos]);
return;
}
expand(pos);
int mid=(r+l)/2;
update(pos*2+1,l,mid,left,right);
update(pos*2+2,mid+1,r,left,right);
merge(pos);
}
void init(int N, int M, std::vector<int> P, std::vector<int> A){
n=N;m=M;
for (int i = 0; i < M; ++i) a[i]=A[i];
build(0,0,m-1);
}
int count_ways(int L, int R) {
L-=n;R-=n;
update(0,0,m-1,L,R);
return dp[1][0];
}
