#include <iostream>
#include <vector>
using namespace std;
#define ll long long
#define MOD (ll)1000002022
vector<int> a;
struct segTree{
ll l, r;
segTree* lc, *rc;
ll lazy;
ll way0;
ll way1;
segTree(ll st){
l = r = st;
lc = rc = nullptr;
lazy = 0;
way0 = (a[st] == 0);
way1 = (a[st] == 1);
}
segTree(segTree*le, segTree*ri){
lc = le; rc = ri;
l = lc->l;
r = rc->r;
lazy = 0;
way0 = (((lc->way1 * rc->way0)%MOD) + ((lc->way0 * rc->way1)%MOD) + (2*(lc->way0 * rc->way0)%MOD))%MOD;
way1 = (((lc->way1 * rc->way0)%MOD) + ((lc->way0 * rc->way1)%MOD) + (2*(lc->way1 * rc->way1)%MOD))%MOD;
}
};
segTree * build(ll l, ll r){
if(l == r) return new segTree(l);
ll mid = (l+r)/2;
return new segTree(build(l, mid), build(mid+1, r));
}
ll update(segTree * st, ll l, ll r){
if(st->lazy){
swap(st->way0, st->way1);
if(l!=r){
st->rc->lazy = !st->rc->lazy;
st->lc->lazy = !st->lc->lazy;
}
st->lazy = 0;
}
if(st->l == l && st->r == r){
st->lazy = !st->lazy;
if(st->lazy){
swap(st->way0, st->way1);
if(l!=r){
st->rc->lazy = !st->rc->lazy;
st->lc->lazy = !st->lc->lazy;
}
st->lazy = 0;
}
return st->way1;
}
ll mid = (st->l + st->r)/2;
if(l <= mid) update(st->lc, l, min(r, mid));
if(r > mid) update(st->rc, max(l, mid+1), r);
ll l0, l1, r0, r1;
l0 = st->lc->way0;
l1 = st->lc->way1;
r0 = st->rc->way0;
r1 = st->rc->way1;
if(st->lc->lazy) swap(l0, l1);
if(st->rc->lazy) swap(r0, r1);
st->way0 = (((l1*r0)%MOD) + ((l0*r1)%MOD) + ((2*(r0*l0))%MOD))%MOD;
st->way1 = (((l1*r0)%MOD) + ((l0*r1)%MOD) + ((2*(r1*l1))%MOD))%MOD;
return st->way1;
}
ll n, m;
segTree*sg;
void init(int N, int M, vector<int> p, vector<int> A){
a = A;
n = N;
m = M;
sg = build(0, m-1);
return;
}
int count_ways(int L, int R){
return update(sg, L-n, R-n);
}
