#include "circuit.h"
#include <algorithm>
#include <functional>
#include <iostream>
#include <vector>
using ull = unsigned long long;
const int MOD = 1000002022;
int N, M;
std::vector<int> val;
std::vector<int> S0, S1, tag;
void update(int o) {
S0[o] = (S0[o << 1] + S0[o << 1 | 1]) % MOD;
S1[o] = (S1[o << 1] + S1[o << 1 | 1]) % MOD;
}
void apply(int o) {
tag[o] ^= 1;
std::swap(S0[o], S1[o]);
}
void push(int o) {
if (tag[o]) {
apply(o << 1); apply(o << 1 | 1);
tag[o] = 0;
}
}
void modify(int o, int L, int R, int l, int r) {
if (L == l && R == r) return apply(o);
push(o);
int mid = (L + R) >> 1;
if (r <= mid) modify(o << 1, L, mid, l, r);
else if (l > mid) modify(o << 1 | 1, mid + 1, R, l, r);
else {
modify(o << 1, L, mid, l, mid);
modify(o << 1 | 1, mid + 1, R, mid + 1, r);
}
update(o);
}
void init(int _N, int _M, std::vector<int> P, std::vector<int> A) {
N = _N; M = _M;
std::vector<int> prod(N + M);
std::fill(prod.begin() + N, prod.end(), 1);
for (int i = 1; i != N + M; ++i) ++prod[P[i]];
for (int i = N - 1; i; --i) prod[P[i]] = prod[P[i]] * (ull)prod[i] % MOD;
std::vector<std::vector<int>> ch(N);
for (int i = 1; i != N + M; ++i) ch[P[i]].push_back(i);
val.resize(N + M);
val[0] = 1;
for (int i = 0; i != N; ++i) {
int prd = 1;
std::vector<int> tmp;
for (int j : ch[i]) {
tmp.push_back(prd);
prd = prd * (ull)prod[j] % MOD;
}
prd = val[i]; std::reverse(ch[i].begin(), ch[i].end());
for (int j : ch[i]) {
val[j] = tmp.back() * (ull)prd % MOD;
prd = prd * (ull)prod[j] % MOD;
tmp.pop_back();
}
}
val.erase(val.begin(), val.begin() + N);
S0.resize(M << 2); S1.resize(M << 2); tag.resize(M << 2);
std::function<void(int, int, int)> build = [&](int o, int L, int R) {
if (L == R) {
S0[o] = val[L]; S1[o] = 0;
if (A[L]) std::swap(S0[o], S1[o]);
return;
}
int mid = (L + R) >> 1;
build(o << 1, L, mid); build(o << 1 | 1, mid + 1, R);
update(o);
};
build(1, 0, M - 1);
}
int count_ways(int L, int R) {
L -= N; R -= N;
modify(1, 0, M - 1, L, R);
return S1[1];
}
