#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <numeric>
using namespace std;
typedef long long int ll;
typedef vector<int> stdvi;
typedef vector<ll> vi;
typedef vector<vi> vvi;
typedef pair<ll, ll> pi;
typedef vector<pi> vpi;
typedef vector<bool> vb;
const ll big_mod = 1000002022;
ll N;
ll M;
vi A;
vi P;
vvi Q;
vpi segtree;
vpi left_right;
vb lazy;
pi combine(pi a, pi b) {
return make_pair( (a.first + b.first) % big_mod, (a.second + b.second) % big_mod);
}
pi flip(pi a) {
return make_pair( (big_mod + a.second - a.first) % big_mod, a.second);
}
void lazy_propagation(int x) {
if (lazy[x]) {
segtree[x] = flip(segtree[x]);
lazy[x] = false;
if (left_right[x].first != left_right[x].second) {
lazy[2 * x] = !lazy[2 * x];
lazy[2 * x + 1] = !lazy[2 * x + 1];
}
}
}
void update(int x, int l, int r) { // flip all in the interval [l, r]
lazy_propagation(x);
if ((left_right[x].first > r) || (l > left_right[x].second)) {
return;
}
if ((l <= left_right[x].first) && (left_right[x].second <= r)) {
lazy[x] = true;
lazy_propagation(x);
return;
}
update(2 * x, l, r);
update(2 * x + 1, l, r);
segtree[x] = combine(segtree[2 * x], segtree[2 * x + 1]);
}
pi query(int x, int l, int r) {
lazy_propagation(x);
if ((left_right[x].first > r) || (l > left_right[x].second)) {
return make_pair((ll)0, (ll)0);
}
if ((l <= left_right[x].first) && (left_right[x].second <= r)) {
return segtree[x];
}
return combine(query(2 * x, l, r), query(2 * x + 1, l, r));
}
vi B;
void build(int x, int l, int r) {
left_right[x] = make_pair(l, r);
lazy[x] = false;
if (l == r) {
segtree[x] = make_pair(A[l] * B[l], B[l]);
return;
}
int m = (l + r) / 2;
build(2 * x, l, m);
build(2 * x + 1, m + 1, r);
segtree[x] = combine(segtree[2 * x], segtree[2 * x + 1]);
}
vi dp;
ll calc_dp(int cur) {
if (cur >= N) {
return (ll)1;
}
ll n = (ll)Q[cur].size();
if (n == 1) {
dp[Q[cur][0]] = 1;
return calc_dp(Q[cur][0]);
}
vi children(n);
for (int i = 0; i < n; i++) {
children[i] = calc_dp(Q[cur][i]);
}
vi left(n);
vi right(n);
left[0] = children[0];
right[n - 1] = children[n - 1];
for (int i = 1; i < n; i++) {
left[i] = (left[i - 1] * children[i]) % big_mod;
right[n - 1 - i] = (right[n - i] * children[n - 1 - i]) % big_mod;
}
dp[Q[cur][0]] = right[1];
for (int i = 1; i < n - 1; i++) {
dp[Q[cur][i]] = (left[i - 1] * right[i + 1]) % big_mod;
}
dp[Q[cur][n - 1]] = left[n - 2];
return (right[0] * n) % big_mod;
}
void calc_delta(int cur, ll product_above) {
product_above *= dp[cur];
product_above %= big_mod;
if (cur >= N) {
B[cur - N] = product_above;
return;
}
for (vi::iterator child = Q[cur].begin(); child != Q[cur].end(); child++) {
calc_delta(*child, product_above);
}
}
void init(int N_, int M_, stdvi P_, stdvi A_) {
N = N_;
M = M_;
//cout << "one" << endl;
A.resize(M);
for (int i = 0; i < M; i++) {
A[i] = (ll)A_[i];
}
//cout << "two" << endl;
P.resize(N + M);
for (int i = 0; i < N + M; i++) {
P[i] = (ll)P_[i];
}
//cout << "three" << endl;
Q.resize(N);
for (int i = 1; i < N + M; i++) {
Q[P[i]].push_back(i);
}
//cout << "four" << endl;
B.resize(M);
// now we install B[i] with the delta which node N + i inflicts upon the root...
//cout << "five" << endl;
dp.resize(N + M);
calc_dp(0);
dp[0] = 1;
/*
for (auto t : dp) {
cout << t << " ";
}
cout << endl;
*/
calc_delta(0, 1);
/*
for (auto t : B) {
cout << t << " ";
}
cout << endl;
*/
segtree.resize(4 * M);
left_right.resize(4 * M);
lazy.resize(4 * M);
build(1, 0, M - 1);
/*
for (int i = 0; i < segtree.size(); i++) {
cout << "(" << segtree[i].first << ", " << segtree[i].second << " : " << left_right[i].first << ", " << left_right[i].second << " " << lazy[i] << ") ";
}
cout << endl;
for (auto t : segtree) {
cout << "(" << t.first << ", " << t.second << ") ";
}
cout << endl;
*/
}
int count_ways(int L, int R) {
update(1, L - N, R - N);
/*
for (int i = 0; i < segtree.size(); i++) {
cout << "(" << segtree[i].first << ", " << segtree[i].second << " : " << left_right[i].first << ", " << left_right[i].second << " " << lazy[i] << ") ";
}
cout << endl;
for (auto t : segtree) {
cout << "(" << t.first << ", " << t.second << ") ";
}
cout << endl;
*/
return (int)query(1, 0, M - 1).first;
}
/*
int main() {
int N_ = 3;
int M_ = 4;
stdvi P_ = {-1, 0, 1, 2, 1, 1, 0};
stdvi A_ = {1, 0, 1, 0};
int N_ = 1;
int M_ = 100;
stdvi P_ = {-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
stdvi A_ = {1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0};
init(N_, M_, P_, A_);
//cout << count_ways(3, 4) << endl;
//cout << count_ways(4, 5) << endl;
cout << count_ways(0, 76) << endl;
cout << count_ways(2, 54) << endl;
cout << count_ways(1, 101) << endl;
cout << count_ways(49, 80) << endl;
cout << count_ways(79, 79) << endl;
}
*/
