#include "circuit.h"
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
#include <iterator>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using std::array;
using std::pair;
using std::string;
using std::tuple;
using std::vector;
using ll = long long;
constexpr int inf = (1 << 30) - 1;
constexpr ll infll = (1ll << 62) - 1;
template <class F> struct make_fixed : private F {
explicit make_fixed(F&& f) : F(std::forward<F>(f)) {}
template <class... Args> decltype(auto) operator()(Args&&... args) const {
return F::operator()(*this, std::forward<Args>(args)...);
}
};
template <class T, class... Args> void DBG(const T& x, const Args&... args) {
std::cerr << x;
if constexpr (sizeof...(args)) {
std::cerr << ' ';
DBG(args...);
} else {
std::cerr << std::endl;
}
}
template <class T> void DBG(const std::vector<T>& v) {
std::cerr << '[';
bool f = false;
for (const T& x : v) {
if (f) std::cerr << ", ";
f = true;
std::cerr << x;
}
std::cerr << ']' << std::endl;
}
constexpr int mod = 1000002022;
struct Fp {
Fp() : x(0) {}
Fp(int x) : x(x) {}
Fp& operator+=(const Fp& t) {
if ((x += t.x) >= mod) x -= mod;
return *this;
}
Fp& operator-=(const Fp& t) {
if ((x -= t.x) < 0) x += mod;
return *this;
}
Fp& operator*=(const Fp& t) {
x = (ll)x * t.x % mod;
return *this;
}
Fp operator+(const Fp& t) const { return Fp(*this) += t; }
Fp operator-(const Fp& t) const { return Fp(*this) -= t; }
Fp operator*(const Fp& t) const { return Fp(*this) *= t; }
int get() const { return x; }
friend std::ostream& operator<<(std::ostream& os, const Fp& t) { return os << t.x; }
private:
int x;
};
struct segment_tree {
segment_tree() = default;
explicit segment_tree(vector<pair<Fp, Fp>> init) {
logn = 0;
while ((1 << logn) < (int)init.size()) logn += 1;
size = 1 << logn;
data.resize(2 * size);
sub.resize(2 * size);
flip.resize(size);
for (int i = 0; i < (int)init.size(); ++i) std::tie(data[i + size], sub[i + size]) = init[i];
for (int i = size - 1; i > 0; --i) fetch(i);
}
void range_flip(int l, int r) {
l += size;
r += size;
push(l);
push(r);
for (int s = l, t = r; s < t; s >>= 1, t >>= 1) {
if (s & 1) apply(s++);
if (t & 1) apply(--t);
}
pull(l);
pull(r);
}
Fp get() const { return data[1]; }
private:
int size, logn;
vector<Fp> data, sub;
vector<char> flip;
void fetch(int i) {
data[i] = data[2 * i] + data[2 * i + 1];
sub[i] = sub[2 * i] + sub[2 * i + 1];
}
void apply(int i) {
std::swap(data[i], sub[i]);
if (i < size) flip[i] ^= 1;
}
void flush(int i) {
if (flip[i]) {
apply(2 * i);
apply(2 * i + 1);
flip[i] = false;
}
}
void push(int i) {
int rz = __builtin_ctz(i);
for (int d = logn; d > rz; --d) flush(i >> d);
}
void pull(int i) {
i >>= __builtin_ctz(i);
while (i >>= 1) fetch(i);
}
};
int N_memo;
segment_tree seg;
void init(int N, int M, vector<int> P, vector<int> A) {
N_memo = N;
vector<vector<int>> child(N + M);
for (int i = 1; i < N + M; ++i) child[P[i]].push_back(i);
vector<Fp> ways(N + M, 1);
for (int i = N - 1; i >= 0; --i) {
ways[i] = (int)child[i].size();
for (const int j : child[i]) ways[i] *= ways[j];
}
vector<Fp> coeff(N + M, 1);
for (int i = 0; i < N; ++i) {
const int n = (int)child[i].size();
vector<Fp> suff(n);
suff[n - 1] = 1;
for (int k = n - 1; k > 0; --k) suff[k - 1] = suff[k] * ways[child[i][k]];
Fp pref = coeff[i];
for (int k = 0; k < n; ++k) {
coeff[child[i][k]] = pref * suff[k];
pref *= ways[child[i][k]];
}
}
vector<pair<Fp, Fp>> data(M);
for (int i = 0; i < M; ++i) {
if (A[i]) data[i] = {coeff[i + N], 0};
else data[i] = {0, coeff[i + N]};
}
seg = segment_tree(std::move(data));
}
int count_ways(int L, int R) {
seg.range_flip(L - N_memo, R - N_memo + 1);
return seg.get().get();
}
