#include "circuit.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#define int long long
#define pii pair<int,int>
#define vi vector<int>
#define ff first
#define ss second
#define sp << " " <<
#define all(x) x.begin(),x.end()
#define big(x) ((int)(x.size()))
using namespace std;
const int MOD = 1'000'002'022, LIM = 1e6+1, inf = 2e9;
int add(int x,int y) {
if ((x + y) >= MOD) return x + y - MOD;
return x + y;
}
int mult(int x,int y) {
return (1LL * x * y) % MOD;
}
int expo(int x,int y) {
if (!y) return 1;
int e = expo(x,y/2);
e = mult(e,e);
if (y&1) e= mult(e,x);
return e;
}
//range toggle mass sum
struct ST {
vector<pii> t;
vi lazy;
void build(int node,int l,int r) {
if (l > r) return;
lazy[node] = 0;
t[node] = {0,r-l+1};
if (l == r) return;
int m = (l+r) >> 1;
build(2*node,l,m),build(2*node+1,m+1,r);
}
ST(){}
ST(int nn) {
t.resize(4*nn+1);
lazy.resize(4*nn+1);
build(1,1,nn);
}
void push(int node,bool leaf) {
if (!lazy[node]) return;
t[node].ff = t[node].ss-t[node].ff;
if (!leaf) {
lazy[2*node]^=1;
lazy[2*node+1]^=1;
}
lazy[node] = 0;
}
void update(int node,int l,int r,int L,int R) {
push(node,l==r);
if (l > R || r < L) return;
if (l >=L && r <= R) {
lazy[node]^=1;
push(node,l==r);
return;
}
int m = (l+r) >> 1;
update(2*node,l,m,L,R),update(2*node+1,m+1,r,L,R);
t[node].ff = t[2*node].ff+t[2*node+1].ff;
}
int query(int node,int l,int r,int L,int R) {
push(node,l==r);
if (l > R || r < L) return 0;
if (l >= L && r <= R) return t[node].ff;
int m = (l+r) >> 1;
return query(2*node,l,m,L,R),query(2*node+1,m+1,r,L,R);
}
} st;
int nn;
int mm;
void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
st = ST(M);
mm = M;
nn = N;
for (int i = 0;i<M;i++) if (A[i]) st.update(1,1,M,i+1,i+1);
}
int32_t count_ways(int32_t L, int32_t R) {
L-=nn,R-=nn;
st.update(1,1,mm,L+1,R+1);
return add(expo(2,st.query(1,1,mm,1,mm)),MOD-1);
}
