#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){ //this function updates ST according to the call and returns the value of node 0:1
if(st->lazy){ // first, push lazy in this node down. This helps remove confusion.
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){ //in this case, we have reached the node we wanted.
st->lazy = !st->lazy; // make a lazy and push it down.
if(st->lazy){
swap(st->way0, st->way1);
if(l!=r){ //checks if it is a leaf node. If yes, it doesn't have children.
st->lc->lazy = !st->lc->lazy;
st->rc->lazy = !st->rc->lazy; //edit children's lazy
}
st->lazy = 0; //done!
}
return st->way1; // of course this will only be accessed if L = 0 and R = M-1
}
ll mid = (st->l + st->r)/2; //select the mid in the node we are in.
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); // get left node's values and edit if necessary.
if(st->rc->lazy) swap(r0, r1); // get right node's values and edit if necessary.
st->way0 = (((l1*r0)%MOD) + ((l0*r1)%MOD) + ((2*(r0*l0))%MOD))%MOD; // build this node
st->way1 = (((l1*r0)%MOD) + ((l0*r1)%MOD) + ((2*(r1*l1))%MOD))%MOD;
return st->way1; // return value! :)
}
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);
}
