#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define x first
#define y second
#define pb push_back
#define loop(i,s,e) for(int i=s;i<e;i++)
#define loopr(i,s,e) for(int i=e-1;i>=s;i--)
#define chkmax(a,b) a=max(a,b)
#define chkmin(a,b) a=min(a,b)
#define all(a) a.begin(),a.end()
const int mod = 1000002022;
int n,m;
vvi adj;
vi a;
//vi cnt_st, cnt_h;
vi mul;
struct seg{
int l,r,mid;
int cnt0=0, cnt1=0;
seg *lp, *rp;
bool flag=0;
void init(int l_, int r_){
l=l_; r=r_;
mid = (l+r)/2;
if(l+1 < r){
lp = new seg();
rp = new seg();
lp->init(l,mid);
rp->init(mid,r);
}
}
void set(){
int tmp = cnt0;
cnt0 = cnt1;
cnt1 = tmp;
flag=!flag;
}
void push(){
if(flag){
lp->set();
rp->set();
flag=0;
}
}
void pull(){
cnt1 = ((lp->cnt0 * rp->cnt1)%mod + (lp->cnt1 * rp->cnt0)%mod + (2*lp->cnt1*rp->cnt1)%mod)%mod;
cnt0 = ((lp->cnt0 * rp->cnt1)%mod + (lp->cnt1 * rp->cnt0)%mod + (2*lp->cnt0*rp->cnt0)%mod)%mod;
}
void update_swap(int a, int b){
if(a<=l && r<=b){
set();
return;
}
if(l>=b || r<=a) return;
push();
lp->update_swap(a,b);
rp->update_swap(a,b);
pull();
}
void update(int ind, int val){
if(l==r-1){
if(val){
cnt1=1; cnt0=0;
}
else{
cnt0=1; cnt1=0;
}
return;
}
if(ind<mid) lp->update(ind,val);
else rp->update(ind,val);
pull();
}
int query(){
return cnt1;
}
};
seg sg;
void init(int32_t N, int32_t M, std::vector<int32_t> P, std::vector<int32_t> A) {
n=N;m=M;
adj.resize(n+m);
loop(i,1,n+m){
adj[P[i]].pb(i);
}
a.resize(n+m);
sg.init(0,m);
loop(i,0,m){
sg.update(i,A[i]);
a[i+n] = A[i];
}
}
int32_t count_ways(int32_t L, int32_t R) {
int l=L, r=R;
l-=n; r-=n;
sg.update_swap(l,r+1);
return sg.query();
}
