#include "circuit.h"
#include <algorithm>
#include <iostream>
#include <vector>
using ull = unsigned long long;
const int MOD = 1000002022;
int N, M;
std::vector<int> A, val;
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;
A.resize(N + M);
std::copy(_A.begin(), _A.end(), A.begin() + N);
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();
}
}
}
int count_ways(int L, int R) {
for (int i = L; i <= R; ++i) A[i] = !A[i];
int sum = 0;
for (int i = N; i != N + M; ++i) if (A[i]) sum = (sum + val[i]) % MOD;
return sum;
}
