#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<bool> vb;
typedef vector<int> vi;
typedef vector<i32> vi32;
typedef vector<vi> vvi;
constexpr int MOD = 1'000'002'022;
vvi children;
int n, m;
vb a;
void init(i32 N, i32 M, vi32 P, vi32 A)
{
n = N;
m = M;
children = vvi(N);
a = vb(M);
loop(sz(P), i)
{
if (i == 0)
continue;
children[P[i]].pb(i);
}
loop(sz(A), i)
{
a[i] = A[i];
}
}
ii calc(int i)
{
if (i >= n)
{
if (a[i - n])
return {1, 1};
return {1, 0};
}
int all = sz(children[i]), r1 = 0;
vi alls, ones;
vi prefProd;
vi sufProd;
for (int j : children[i])
{
auto [allJ, v1] = calc(j);
all *= allJ;
all %= MOD;
alls.pb(allJ);
ones.pb(v1);
}
loop(sz(children[i]), j)
{
int allExcept = 1;
loop(sz(children[i]), k)
{
if (j == k)
continue;
allExcept *= alls[k];
allExcept %= MOD;
}
r1 += allExcept * ones[j];
r1 %= MOD;
}
if (sz(children[i]) == 2)
{
assert(all == (2 * alls[0] * alls[1]) % MOD);
assert(r1 == (alls[0] * ones[1] + ones[0] * alls[1]) % MOD);
}
return {all % MOD, r1 % MOD};
}
i32 count_ways(i32 L, i32 R)
{
for (int i = L; i <= R; i++)
{
a[i - n].flip();
}
return calc(0)[1];
}
