#include "circuit.h"
#pragma GCC optimize("trapv")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define loop(x, i) for (int i = 0; i < x; i++)
#define rev(x, i) for (int i = (int)x - 1; i >= 0; i--)
#define ALL(x) begin(x), end(x)
#define sz(x) (int)x.size()
typedef signed i32;
typedef array<int, 2> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;
typedef vector<int> vi;
typedef vector<i32> vi32;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
constexpr int MOD = 1'000'002'022;
vvi children;
vi term01;
int n, m;
vb a;
vi c_i;
/*struct val
{
void swap()
{
}
val operator+(const val &b)
{
val a = *this, res;
return res;
}
};
vector<val> tree;
vb lazy;
void pull(int i)
{
tree[i] = tree[2 * i] + tree[2 * i + 1];
}
void push(int i)
{
}
val operation(int i, int l, int r, int ql, int qr, int op)
{
push(i);
if (r < ql || qr < l)
return {};
if (ql <= l && r <= qr)
{
if (op == 1)
{
lazy[i] = 1;
push(i);
}
return tree[i];
}
int m = (l + r) / 2;
val res = operation(2 * i, l, m, ql, qr, op) +
operation(2 * i + 1, m + 1, r, ql, qr, op);
pull(i);
return tree[i];
};*/
int calc01s(int i)
{
if (i >= n)
{
return term01[i] = 1;
}
int all = sz(children[i]);
for (int j : children[i])
{
int v = calc01s(j);
all *= v;
all %= MOD;
}
return term01[i] = all;
}
vii calc(int i)
{
if (i >= n)
{
return {{i, 1}};
}
int r1 = 0;
int c = sz(children[i]);
vi ones;
vi prod, prefProd(c + 1, 1), sufProd(c + 1, 1);
vvii vs;
for (int j : children[i])
{
vii cur = calc(j);
vs.pb(cur);
prod.pb(term01[j]);
}
loop(c, j)
{
prefProd[j + 1] = prefProd[j] * prod[j];
}
rev(c, j)
{
sufProd[j] = sufProd[j + 1] * prod[j];
}
vii res;
loop(c, j)
{
vii cur = vs[j];
int mult = (prefProd[j] * sufProd[j + 1]) % MOD;
for (auto [ix, v] : cur)
{
res.pb({ix, (v * mult) % MOD});
}
}
return res;
}
void init(i32 N, i32 M, vi32 P, vi32 A)
{
n = N;
m = M;
children = vvi(N);
term01 = vi(N + M);
a = vb(M);
loop(sz(P), i)
{
if (i == 0)
continue;
children[P[i]].pb(i);
}
loop(sz(A), i)
{
a[i] = A[i];
}
calc01s(0);
vii terms = calc(0);
sort(ALL(terms));
c_i = vi(m);
for (auto [i, v] : terms)
c_i[i - n] = v;
}
i32 count_ways(i32 L, i32 R)
{
for (int i = L; i <= R; i++)
{
a[i - n].flip();
}
int res = 0;
loop(m, i)
{
res += c_i[i] * a[i];
res %= MOD;
}
return res;
}
