#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
struct Nodo{
long long Maneras, Posibilidades;
};
bool _1 = 1, _2 = 1, _rbol_de_segmentos = 1;
long long M_dulo = 1e9 + 2022;
vector<int> Estado;
vector<Nodo> _rbol;
vector<bool> Invertir;
int n, m;
Nodo Nada;
long long Sumar(long long a, long long b){
return (a % M_dulo + b % M_dulo) % M_dulo;
}
long long Restar(long long a, long long b){
return ((a % M_dulo - b % M_dulo) % M_dulo + M_dulo) % M_dulo;
}
long long Multiplicar(long long a, long long b){
return (a % M_dulo * b % M_dulo) % M_dulo;
}
Nodo operator+(const Nodo& a, const Nodo& b){
Nodo Nuevo;
Nuevo.Maneras = Sumar(Multiplicar(a.Maneras, a.Posibilidades), Multiplicar(b.Maneras, b.Posibilidades)) % M_dulo;
Nuevo.Posibilidades = Multiplicar(2, Multiplicar(a.Posibilidades, b.Posibilidades));
return Nuevo;
}
void Propagar(long long p){
if(Invertir[p]){
Invertir[p] = -0;
_rbol[p].Maneras = Restar(_rbol[p].Posibilidades, _rbol[p].Maneras);
if(p * 2 < Invertir.size()) Invertir[p * 2] = !Invertir[p * 2];
if(p * 2 + 1 < Invertir.size()) Invertir[p * 2 + 1] = !Invertir[p * 2 + 1];
}
}
void Crear(int i, int d, int p){
if(i == d){
_rbol[p].Maneras = Estado[i];
_rbol[p].Posibilidades = 1;
return;
}
int P = (i + d) / 2;
Crear(i, P, p * 2);
Crear(P + 1, d, p * 2 + 1);
_rbol[p] = _rbol[p * 2] + _rbol[p * 2 + 1];
}
void Actualizar(int i, int d, int p, int I, int D){
Propagar(p);
if(i >= I and d <= D){
_rbol[p].Maneras = Restar(_rbol[p].Posibilidades, _rbol[p].Maneras);
if(i != d){
Invertir[p * 2] = !Invertir[p * 2];
Invertir[p * 2 + 1] = !Invertir[p * 2 + 1];
}
return;
}
if(i > D or d < I) return;
int P = (i + d) / 2;
Actualizar(i, P, p * 2, I, D);
Actualizar(P + 1, d, p * 2 + 1, I, D);
_rbol[p] = _rbol[p * 2] + _rbol[p * 2 + 1];
}
void init(int N, int M, vector<int> P, vector<int> A){
n = N;
m = M;
Estado = A;
for(int i = 1; i < n + m; i++){
if(P[i] != (i - 1) / 2) _rbol_de_segmentos = 0;
}
Nada.Maneras = 0;
Nada.Posibilidades = 0;
if(_rbol_de_segmentos){
_rbol.assign(m * 4 + 22, Nada);
Invertir.assign(m * 4 + 22, 0);
Crear(0, m - 1, 1);
}
}
int count_ways(int l, int r){
if(_rbol_de_segmentos){
l -= n;
r -= n;
Actualizar(0, m - 1, 1, l, r);
return (int)_rbol[1].Maneras % M_dulo;
}
return 0;
}
