#include "circuit.h"
//#pragma GCC optimize("O3")
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using arr = array<ll, 2>;
using arrr = array<int, 3>;
constexpr ll mod = 1e9 + 2022;
constexpr int maxn = 2e5;
void fmod(ll &val)
{
if (val >= mod) val %= mod;
}
int n, m;
basic_string <int> children[maxn];
ll subtree[maxn] = { 0 }, vals[maxn];
ll find_subtree_vals(int p)
{
ll v = children[p].size();
for (int i : children[p])
{
v *= find_subtree_vals(i);
fmod(v);
}
subtree[p] = v;
if (v == 0) subtree[p] = 1;
return subtree[p];
}
void get_vals(int p)
{
int g = children[p].size();
vector<ll> l(g + 1, vals[p]), r(g + 1, 1);
for (int i = 1; i <= g; i++) {
l[i] = l[i - 1] * subtree[children[p][i - 1]]; fmod(l[i]);
}
for (int i = g - 1; i >= 0; i--) {
r[i] = r[i + 1] * subtree[children[p][i]]; fmod(r[i]);
}
// cout << "P" << p << " " << vals[p] << "\n";
// for (int i : l) cout << i << " ";
// cout << "\n";
// for (int i : r) cout << i << " ";
// cout << "\n";
for (int i = 0; i < g; i++)
{
vals[children[p][i]] = l[i] * r[i + 1];
fmod(vals[children[p][i]]);
}
for (int i : children[p]) get_vals(i);
}
constexpr int siz = 1 << 17;
arr segtree[siz * 2] = { 0 };
bool flipped[siz * 2] = { 0 };
arr merge(arr ap, arr bp)
{
ap[0] += bp[0], ap[1] += bp[1];
fmod(ap[0]), fmod(ap[1]);
return ap;
}
void print()
{
for (int i = 1; i < 2 * siz; i++)
{
if (__builtin_popcount(i) == 1) cout << "\n";
cout << segtree[i][0] << " ";
}
cout << endl;
}
void init(int N, int M, std::vector<int> p, std::vector<int> a) {
n = N, m = M;
for (int i = 1; i < n + m; i++)
{
children[p[i]].push_back(i);
}
find_subtree_vals(0);
vals[0] = 1;
get_vals(0);
// for (int i = 0; i < n + m; i++) cout << subtree[i] << " ";
// cout << "\n";
// for (int i = 0; i < n + m; i++) cout << vals[i] << " ";
// cout << "\n";
for (int i = 0; i < m; i++)
{
segtree[i + siz][1] = vals[i + n]; // Doesn't work with modulo
if (a[i]) segtree[i + siz][0] = segtree[i + siz][1];
}
for (int i = siz - 1; i > 0; i--)
{
segtree[i] = merge(segtree[i * 2], segtree[i * 2 + 1]);
}
}
void update(int p, int sl, int sr, int gl, int gr)
{
if (flipped[p])
{
segtree[p][0] = segtree[p][1] - segtree[p][0];
if (segtree[p][0] < 0) segtree[p][0] += mod;
if (p < siz) flipped[p * 2] ^= 1, flipped[p * 2 + 1] ^= 1;
flipped[p] ^= 1;
}
// cout << p << " " << sl << " " << sr << " " << gl << " " << gr << " \n";
if (gl <= sl && sr <= gr) {
segtree[p][0] = segtree[p][1] - segtree[p][0];
if (segtree[p][0] < 0) segtree[p][0] += mod;
if (p < siz) flipped[p * 2] ^= 1, flipped[p * 2 + 1] ^= 1;
return ;
}
if (gl > sr || sl > gr) return ;
int mid = (sl + sr) >> 1;
update(p * 2, sl, mid, gl, gr);
update(p * 2 + 1, mid + 1, sr, gl, gr);
segtree[p] = merge(segtree[p * 2], segtree[p * 2 + 1]);
}
int count_ways(int L, int R) {
update(1, 0, siz - 1, L - n, R - n);
return segtree[1][0];
}
