#include "circuit.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <numeric>
namespace ruhan {
using namespace std;
const long long MOD = 1e9 + 2022;
int N, M;
vector<int> P, A;
vector<vector<int>> G;
vector<long long> sub_product;
vector<int> c;
long long multiplier;
struct SegTree {
vector<int> prop, tree;
void init () {
prop.resize(4 * M);
tree.resize(4 * M);
build(1, 0, M - 1);
}
void build (int cn, int b, int e) {
if (b == e) {
tree[cn] = A[b];
return;
}
int m = (b + e) / 2;
build (2 * cn, b, m);
build (2 * cn + 1, m + 1, e);
tree[cn] = tree[2*cn] + tree[2*cn+1];
}
void update (int l, int r) {
update(1, 0, M - 1, l, r, 0);
}
void update (int cn, int b, int e, int l, int r, int px) {
if (r < b || l > e) {
if (px) {
prop[cn] ^= 1;
tree[cn] = e - b + 1 - tree[cn];
}
return;
}
if (l <= b && e <= r) {
//cerr << b << " " << e << " " << l << " " << r << " " << px << "\n";
if (!px) {
prop[cn] ^= 1;
tree[cn] = e - b + 1 - tree[cn];
}
return;
}
px ^= prop[cn];
prop[cn] = 0;
int m = (b + e) / 2;
update(2 * cn, b, m, l, r, px);
update(2 * cn + 1, m + 1, e, l, r, px);
tree[cn] = tree[2*cn] + tree[2*cn+1];
}
int total() const {
return tree[1];
}
} seg_tree;
int Q = 0;
void init45 () {
seg_tree.init();
auto ss = vector<long long>(N + M, 1LL);
for (int u = N - 1; u >= 0; u--) {
int v = 2 * u + 1;
ss[u] = ss[v] * sub_product[u] % MOD;
}
multiplier = ss[1];
//cerr << "multiplier = " << multiplier << "\n";
//cerr << "total = " << seg_tree.total() << "\n";
}
void init (int N_, int M_, vector<int> P_, vector<int> A_) {
N = N_; M = M_; P = P_; A = A_;
//cerr << "N = " << N << "\n";
//cerr << "M = " << M << "\n";
//cerr << "P = ";
//for (int x : P) //cerr << x << " ";
//cerr << "\n";
//cerr << "A = ";
//for (int x : A) //cerr << x << " ";
//cerr << "\n";
c.resize(N);
G.resize(N);
for (int i = N + M - 1; i > 0; i--) {
////cerr << i << " " << P[i] << "\n";
c[P[i]]++;
G[P[i]].push_back(i);
}
sub_product = vector<long long>(N + M, 1);
for (int i = N - 1; i > 0; i--) {
sub_product[i] *= c[i];
sub_product[i] %= MOD;
sub_product[P[i]] *= sub_product[i];
sub_product[P[i]] %= MOD;
}
init45();
}
int subtask123 (int L, int R) {
////cerr << "\n\ncpunt_ways(" << L << ", " << R << ")\n";
for (int i = L - N; i <= R - N; i++) {
A[i] ^= 1;
}
vector<long long> X(N + M, 0LL);
copy(A.begin(), A.end(), X.begin() + N);
for (int u = N - 1; u >= 0; u--) {
vector<vector<long long>> dp(c[u] + 1, vector<long long>(c[u] + 1, 0));
dp[c[u]][0] = 1;
for (int i = c[u] - 1; i >= 0; i--) {
int v = G[u][i];
long long y = (sub_product[v] + MOD - X[v]) % MOD;
dp[i][0] = y * dp[i+1][0] % MOD;
for (int p = 1; p <= c[u]; p++) {
dp[i][p] = X[v] * dp[i+1][p - 1] + y * dp[i+1][p];
dp[i][p] %= MOD;
}
}
X[u] = 0;
for (int p = 1; p <= c[u]; p++) {
X[u] += p * dp[0][p] % MOD;
X[u] %= MOD;
}
////cerr << "X[" << u << "] = " << X[u] << "\n";
}
return X[0];
}
int subtask45 (int L, int R) {
//cerr << "\n\ncount_ways(" << L << ", " << R << ")\n";
seg_tree.update(L - N, R - N);
return (multiplier * seg_tree.total()) % MOD;
}
};
void init(int N, int M, std::vector<int> P, std::vector<int> A) {
ruhan::init(N, M, P, A);
}
int count_ways(int L, int R) {
//return ruhan::subtask123(L, R);
ruhan::Q++;
if (ruhan::N <= 1000 && ruhan::M <= 1000 && ruhan::Q <= 5) return ruhan::subtask123(L, R);
else return ruhan::subtask45(L, R);
}
