#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000002022;
int n, m;
vector<pair<ll, ll>> segTree(2e5 + 5, {0, 0});
vector<bool> lazy(2e5 + 5, false);
pair<ll, ll> merge(pair<ll, ll> a, pair<ll, ll> b) {
pair<ll, ll> res = {0, 0};
(res.first += (2 * a.first * b.first)) %= MOD;
(res.first += (a.first * b.second + a.second * b.first)) %= MOD;
(res.second += (a.first * b.second + a.second * b.first)) %= MOD;
(res.second += (2 * a.second * b.second)) %= MOD;
return res;
}
void push_down(int cur, int treeLeft, int treeRight) {
if (!lazy[cur]) return;
swap(segTree[cur].first, segTree[cur].second);
lazy[cur] = false;
if (treeLeft == treeRight) return;
lazy[cur * 2 + 1] = !lazy[cur * 2 + 1];
lazy[cur * 2 + 2] = !lazy[cur * 2 + 2];
}
void setup(int cur, int treeLeft, int treeRight, int pos, pair<ll, ll> val) {
if (pos < treeLeft || pos > treeRight) return;
if (treeLeft == treeRight) {
segTree[cur] = val;
return;
}
int mid = (treeLeft + treeRight) / 2;
setup(cur * 2 + 1, treeLeft, mid, pos, val);
setup(cur * 2 + 2, mid + 1, treeRight, pos, val);
segTree[cur] = merge(segTree[cur * 2 + 1], segTree[cur * 2 + 2]);
}
void update(int cur, int treeLeft, int treeRight, int qLeft, int qRight) {
push_down(cur, treeLeft, treeRight);
if (qRight < treeLeft || qLeft > treeRight) return;
if (treeLeft >= qLeft && treeRight <= qRight) {
lazy[cur] = true;
push_down(cur, treeLeft, treeRight);
return;
}
int mid = (treeLeft + treeRight) / 2;
update(cur * 2 + 1, treeLeft, mid, qLeft, qRight);
update(cur * 2 + 2, mid + 1, treeRight, qLeft, qRight);
segTree[cur] = merge(segTree[cur * 2 + 1], segTree[cur * 2 + 2]);
}
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
n = N;
m = M;
for (int i = 0; i < M; ++i) {
if (A[i]) setup(0, 1, M, i + 1, {0, 1});
else setup(0, 1, M, i + 1, {1, 0});
}
// for (int i = 0; i < n + m + 2; ++i) cout << segTree[i].first << ' ' << segTree[i].second << ' ' << lazy[i] << " ";
// cout << endl;
}
int count_ways(int L, int R) {
update(0, 1, m, L - n + 1, R - n + 1);
// for (int i = 0; i < n + m + 2; ++i) cout << segTree[i].first << ' ' << segTree[i].second << ' ' << lazy[i] << " ";
// cout << endl;
return segTree[0].second;
}
