995F - Cowmpany Cowmpensation - CodeForces Solution

#include <bits/stdc++.h>
#define ii pair<int,int>
#define f first
#define s second
#define pb push_back
#define int long long
#define endl '\n'
using namespace std;
const int MAXN = 1e18;
const int mod = 1e9 + 7;
int fact[3005];
int infact[3005];
int pre[3005];
int suf[3005];
int a[3005];
vector<int> w[3005];
int dp[3005][3005];
int n,d;
void DFS(int u)
{
	for(int i = 1;i <= n;i++)
	{
		dp[u][i] = 1;
	}
	for(int v : w[u])
	{
		DFS(v);
		for(int i = 1;i <= n;i++)
		{
			dp[u][i] = (dp[u][i] * dp[v][i]) % mod;
		}
	}
	for(int i = 1;i <= n;i++)
	{
		dp[u][i] = (dp[u][i] + dp[u][i - 1]) % mod;
	}
}
int binpow(int x,int y)
{
	int res = 1;
    while (y > 0) 
	{
        if (y % 2 == 1)
            res = (res * x) % mod;
        y = y >> 1;
        x = (x * x) % mod;
    }
    return res % mod;
}
void AcSolution()
{
	cin >> n >> d;
	dp[1][0] = 0;
	for(int i = 2;i <= n;i++)
	{
		int u;
		cin >> u;
		w[u].push_back(i);
	}
	n++;
	DFS(1);
	for(int i = 1;i <= min(n,d);i++)
	{
		a[i] = dp[1][i];
	}
	if(d <= n)
	{
		cout << a[d] << endl;
		return; 
	}
	pre[0] = 1;
	for(int i = 1;i <= n;i++)
	{
		pre[i] = (pre[i - 1] % mod * (d - i)) % mod;
	}
	suf[n + 1] = 1;
	for(int i = n;i >= 1;i--)
	{
		suf[i] = (suf[i + 1] % mod * (d - i)) % mod;
	} 
	fact[0] = 1;
	for(int i = 1;i <= n;i++)
	{
		fact[i] = ((fact[i - 1] % mod) * i) % mod;
	}
	infact[n] = binpow(fact[n], mod - 2);
    for (int i = n - 1; i >= 0; i--) 
	{
        infact[i] = infact[i + 1] * (i + 1) % mod;
    }
	int res = 0;
	for(int i = 1;i <= n;i++)
	{
		int x = a[i] * pre[i - 1] % mod * suf[i + 1] % mod * infact[n - i] % mod * infact[i - 1] % mod;
		if(i % 2 != n % 2)
		{
			x = -x;
		} 
		res = (res + x + mod) % mod;
	}
	cout << res << endl;
}
signed main()
{
//	freopen("BDIGIT.inp", "r",stdin);
//    freopen("BDIGIT.out", "w",stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
//	cin >> t;
	while(t--)
	{
	 	AcSolution();
	}
}