#include "circuit.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
#define sz(x) int(x.size())
const ll mod = 1'000'002'022;
ll ad(ll a, ll b)
{
return (a+b)%mod;
}
ll mul(ll a, ll b)
{
return (a*b)%mod;
}
const int mx = 200'000;
vll Z(1 + mx, 0);
vll Zprod(1 + mx, 1);
vll coeff(1 + mx, 0);
vi children[1 + mx];
int N, M;
vi A;
ll res = 0;
void dfs(int u)
{
for(int v : children[u])
{
Z[u]++;
dfs(v);
if(Z[v] != 0)
Zprod[u] = mul(Zprod[u], Zprod[v]);
}
if(Z[u] != 0)
Zprod[u] = mul(Zprod[u], Z[u]);
// cerr << u << " : " << Z[u] << " | " << Zprod[u] << '\n';
}
void dfs2(int u, ll curr)
{
coeff[u] = curr;
// cerr << u << " -> " << curr << '\n';
ll fwd[1 + sz(children[u]) + 1];
ll bwd[1 + sz(children[u]) + 1];
fwd[0] = 1;
for(int e = 1; e <= sz(children[u]); e++)
fwd[e] = mul(fwd[e-1], Zprod[ children[u][e - 1] ]);
bwd[sz(children[u]) + 1] = 1;
for(int e = sz(children[u]); e >= 1; e--)
bwd[e] = mul(bwd[e+1], Zprod[ children[u][e - 1] ]);
for(int e = 1; e <= sz(children[u]); e++)
{
// cerr << e << " : " << curr << ' ' << fwd[e-1] << ' ' << bwd[e+1] << '\n';
dfs2(children[u][e - 1], mul(curr, mul(fwd[e-1], bwd[e+1])));
}
}
void init(int N_, int M_, vi P_, vi A_)
{
N = N_;
M = M_;
for(int i = 1; i < N+M; i++)
children[P_[i]].push_back(i);
dfs(0);
dfs2(0, 1);
A = vi(N, -1);
for(int a : A_)
A.push_back(a);
// cerr << depth[1] << ' ' << depth[2] << '\n';
for(int i = N; i < N+M; i++)
res = ad(res, mul(A[i], coeff[i]));
// cerr << "res = " << res << '\n';
// for(int f : A)
// cerr << f << '\n';
}
int count_ways(int L, int R)
{
for(int i = L; i <= R; i++)
{
// res = ad(res, mul((!A[i]) - A[i], coeff[i]));
if(A[i] == 0)
res = ad(res, coeff[i]);
else
res = ad(res, mod - coeff[i]);
A[i] = !A[i];
}
return res;
}
