#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
const ll md = 1000002022;
struct segtree{
struct node{
ll A, B, Ar, Br;
bool rev = 0;
node(){
A = 0, B = 1, Ar = 1, Br = 0;
}
node operator+(node X){
node rt;
rt.A = (A*X.B)%md + (X.A*B)%md + (A*X.A*2LL)%md;
rt.A%=md;
rt.B = (A*X.B)%md + (X.A*B)%md + (B*X.B*2LL)%md;
rt.B%=md;
rt.Ar = (Ar*X.Br)%md + (X.Ar*Br)%md + (Ar*X.Ar*2LL)%md;
rt.Ar%=md;
rt.Br = (Ar*X.Br)%md + (X.Ar*Br)%md + (Br*X.Br*2LL)%md;
rt.Br%=md;
return rt;
}
void pushdown(node &X){
if(!rev) return;
X.rev^=rev;
swap(X.A, X.Ar);
swap(X.B, X.Br);
}
};
int k;
vector<node> v;
segtree(int n){
k = 1;
while(k < n) k*=2;
v.resize(2*k, node());
for(int i = k-1; i > 0; i--) v[i] = v[2*i]+v[2*i+1];
}
void update(int l, int r, int nd, int a, int b){
if(a > r || b < l) return;
if(a >= l && b <= r){
v[nd].rev^=1;
swap(v[nd].A, v[nd].Ar);
swap(v[nd].B, v[nd].Br);
return;
}
int mid = (a+b)/2;
v[nd].pushdown(v[2*nd]);
v[nd].pushdown(v[2*nd+1]);
v[nd].rev = 0;
update(l, r, 2*nd, a, mid);
update(l, r, 2*nd+1, mid+1, b);
v[nd] = v[2*nd]+v[2*nd+1];
}
void update(int l, int r){
update(l, r, 1, 0, k-1);
}
ll get(){
return v[1].A;
}
};
int n, m;
vector<int> P, A;
segtree s(0);
void init(int _n, int _m, vector<int> _P, vector<int> _A){
swap(n, _n), swap(m, _m), swap(P, _P), swap(A, _A);
s = segtree(m);
for(int i = 0; i < m; i++) if(A[i]) s.update(i, i);
}
int count_ways(int L, int R){
s.update(L-n, R-n);
return s.get();
}
