#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, treeN = 1;
vi vs;
struct val
{
int v = 0, totalV = 0;
void swap()
{
v = (totalV - v + MOD) % MOD;
}
val operator+(const val &b)
{
val a = *this, res;
res.v = a.v + b.v;
res.totalV = a.totalV + b.totalV;
res.totalV %= MOD;
res.v %= MOD;
return res;
}
};
vector<val> tree;
vb lazy;
void pull(int i)
{
tree[i] = tree[2 * i] + tree[2 * i + 1];
}
void push(int i)
{
if (!lazy[i])
return;
tree[i].swap();
if (i < treeN)
{
lazy[2 * i].flip();
lazy[2 * i + 1].flip();
}
lazy[i] = 0;
}
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 mid = (l + r) / 2;
val res = operation(2 * i, l, mid, ql, qr, op) +
operation(2 * i + 1, mid + 1, r, ql, qr, op);
pull(i);
return res;
};
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;
}
void calc(int i, int mult)
{
if (i >= n)
{
vs[i - n] = mult;
return;
}
int c = sz(children[i]);
vi prod, prefProd(c + 1, 1), sufProd(c + 1, 1);
for (int j : children[i])
{
prod.pb(term01[j]);
}
loop(c, j)
{
prefProd[j + 1] = prefProd[j] * prod[j];
prefProd[j + 1] %= MOD;
}
rev(c, j)
{
sufProd[j] = sufProd[j + 1] * prod[j];
sufProd[j] %= MOD;
}
loop(c, j)
{
int mult2 = (prefProd[j] * sufProd[j + 1]) % MOD;
calc(children[i][j], (mult * mult2) % MOD);
}
}
void init(i32 N, i32 M, vi32 P, vi32 A)
{
n = N;
m = M;
while (treeN < m)
treeN *= 2;
tree.resize(2 * treeN);
lazy.resize(2 * treeN);
children = vvi(N);
term01 = vi(N + M);
vs = vi(M);
loop(sz(P), i)
{
if (i == 0)
continue;
children[P[i]].pb(i);
}
calc01s(0);
calc(0, 1);
loop(m, i)
{
tree[treeN + i].totalV = vs[i];
if (A[i])
tree[treeN + i].v = vs[i];
}
rev(treeN, i) pull(i);
}
i32 count_ways(i32 L, i32 R)
{
operation(1, 0, treeN - 1, L - n, R - n, 1);
return (i32)operation(1, 0, treeN - 1, 0, m - 1, 0).v;
}
