#ifndef davele
#include "circuit.h"
#endif // davele
#include <bits/stdc++.h>
//#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define vi vector <int>
#define pq priority_queue
#define MASK(i) (1ll<<(i))
#define BIT(x, i) (((x) >> (i)) & 1)
#define x0 ___x0
#define y0 ___y0
#define div ___div
#define next ___next
#define prev ___prev
#define left ___left
#define right ___right
#define pos pisosi
#define pb push_back
#define pf push_front
using namespace std;
const int mod = 1e9+2022;
void add (int &a, const int&b){
a+=b;
if (a>=mod) a-=mod;
}
void sub (int&a, const int&b){
a-=b;
if (a<0) a+=mod;
}
void mul (int&a, const int&b){
a = 1ll*a*b%mod;
}
template<class X, class Y>
bool minimize(X &x, const Y&y){
if (x<=y) return false;
else{
x = y;
return true;
}
}
template<class X, class Y>
bool maximize (X &x, const Y&y){
if (x>=y) return false;
else{
x = y;
return true;
}
}
////////////////////////////////////////////////////////////////////////////
const int lim = 21e4, limit = lim+5;
int color[limit], tot[limit], numCom[limit], deg[limit];
int numRoot, numLeaf;
vector <int> adj[limit];
#ifdef davele
void init (int N, int M, int P[], int A[]){
#endif // davele
#ifndef davele
void init (int N, int M, int[] P, int[] A){
#endif // davele
numRoot = N;
numLeaf = M;
for (int i=1; i<N+M; i++){
int u = i, v = P[i];
deg[v]++;
adj[u].pb(v);
adj[v].pb(u);
}
for (int i=0; i<M; i++){
int u = N+i;
color[u] = A[i];
}
}
void dfs (int u, int pre){
//
// tot[u] : so cac bo tham so de dinh u duoc bat
// dp[i]: so cac bo tham so de co i dinh con duoc bat
// notmark : so cac bo tham so de dinh v khong duoc bat
//
if (u>=numRoot){
numCom[u] = 1;
tot[u] = color[u];
return;
}
numCom[u] = deg[u];
vector <int> dp (deg[u]+2, 0);
dp[0] = 1;
int sz = 0;
for (int v:adj[u]){
if (v==pre) continue;
dfs (v, u);
int notmark = numCom[v] - tot[v];
if (notmark<0) notmark+=mod;
mul (numCom[u], numCom[v]);
for (int i=sz; i>=0; i--){
dp[i+1] = (1ll*dp[i]*tot[v]%mod + 1ll*dp[i+1]*notmark%mod)%mod;
}
mul (dp[0], notmark);
sz++;
}
// cerr<<u<<" "<<numCom[u]<<"\n";
tot[u] = 0;
for (int i=1; i<=deg[u]; i++) add(tot[u], 1ll*dp[i]*i%mod);
// cerr<<u<<"\n";
// for (int i=1; i<=deg[u]; i++) cerr<<dp[i]<<" ";
// cerr<<"\n";
}
int count_ways (int L, int R){
for (int i=L; i<=R; i++) color[i] = 1-color[i];
// for (int i=numRoot; i<numRoot+numLeaf; i++) cerr<<i<<" "<<color[i]<<"\n";
dfs(0, 0);
return tot[0];
}
/*
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("circuit.inp", "r", stdin);
freopen("circuit.out", "w", stdout);
int n, m, q;
cin>>n>>m>>q;
int p[n+m+20];
for (int i=0; i<n+m; i++){
// cout<<"Root of "<<i<<": "<<endl;
cin>>p[i];
}
//
int a[m+20];
for (int i=0; i<m; i++){
// cout<<"Val of "<<i+n<<": "<<endl;
cin>>a[i];
}
init(n, m, p, a);
while (q--){
int L, R;
cin>>L>>R;
cout<<count_ways(L, R)<<"\n";
}
}
*/
