#include <bits/stdc++.h>
using namespace std;
//#include "circuit.h"
const int c=500005;
int n, m;
const long long mod=1000002022, phimod=497758632;
int bal[c], jobb[c];
long long ert[c], sum[c], sum2[c], flip[c], po2[c], po223[c], rem[c];
vector<int> sz[c], aa;
long long po(long long a, long long p) {
long long ans=1;
while (p) {
if (p%2) ans=ans*a%mod;
a=a*a%mod;
p/=2;
}
return ans;
}
long long oszt(long long a) {
assert(__gcd(mod, a)==1);
return po(a, phimod-1);
}
void calc(int a) {
int x=2*a, y=2*a+1;
sum[a]=(sum[x]+sum[y])%mod;
sum2[a]=(sum2[x]+sum2[y])%mod;
if (flip[a]) {
swap(sum[a], sum2[a]);
}
}
void seg_tree_init(int m) {
int po=1;
while (po<m) {
po*=2;
}
for (int i=po; i<2*po; i++) {
bal[i]=i-po, jobb[i]=i-po;
if (i-po<m) {
sum[i]=ert[i-po+n], sum2[i]=0;
if (!aa[i-po]) flip[i]=1, swap(sum[i], sum2[i]);
//cout << "fontos " << i << " " << sum[i] << " " << sum2[i] << "\n";
}
}
for (int i=po-1; i>=1; i--) {
bal[i]=bal[2*i], jobb[i]=jobb[2*i+1];
calc(i);
//cout << "kozep " << i << " " << sum[i] << " " << sum2[i] << "\n";
}
}
int h(int a, int l, int r) {
if (bal[a]>r || jobb[a]<l) return 0;
if (l<=bal[a] && jobb[a]<=r) return 2;
return 1;
}
void add(int a, int l, int r) {
int s=h(a, l, r);
if (s==0) return;
if (s==2) {
flip[a]=1-flip[a];
swap(sum[a], sum2[a]);
return;
}
int x=2*a, y=2*a+1;
add(x, l, r), add(y, l, r);
calc(a);
}
void dfs(int a) {
int si=sz[a].size();
long long p2=po2[a], p223=po223[a], val=rem[a];
ert[a]=po(2, p2)*po(223, p223)%mod*val%mod;
//cout << "dfs " << a << " " << ert[a] << "\n";
if (si==0) return;
while (si%2==0) p2--, si/=2;
while (si%223==0) p223--, si/=223;
val=val*oszt(si)%mod;
for (auto x:sz[a]) {
po2[x]=p2, po223[x]=p223, rem[x]=val;
dfs(x);
}
}
void init(int N, int M, vector<int> P, vector<int> A) {
n=N, m=M;
aa=A;
for (int i=1; i<n+m; i++) {
sz[P[i]].push_back(i);
}
rem[0]=1;
for (int i=0; i<n; i++) {
int si=sz[i].size();
while (si%2==0) po2[0]++, si/=2;
while (si%223==0) po223[0]++, si/=223;
rem[0]=rem[0]*si%mod;
}
dfs(0);
seg_tree_init(m);
}
int count_ways(int L, int R) {
L-=n, R-=n;
add(1, L, R);
return sum[1];
}
/*
int main()
{
int a, b;
vector<int> x, y;
cin >> a >> b;
for (int i=0; i<a+b; i++) {
int s;
cin >> s;
x.push_back(s);
}
for (int i=0; i<b; i++) {
int s;
cin >> s;
y.push_back(s);
}
init(a, b, x, y);
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
cout << count_ways(l, r) << "\n";
}
return 0;
}
*/
/*
3 4
-1 0 1 2 1 1 0
1 0 1 0
2
3 4
4 5
*/
