コード
public class LineMST {
private final long MOD = (long) 1e9 + 7;
private long[][] dp;
private int L;
public int count(int N, int L) {
this.L = L;
dp = new long[N + 1][L + 1];
long ans = dp(N, L);
for (int i = 3; i <= N; i++) {
ans = (ans * i) % MOD;
}
return (int) ans;
}
private long dp(int N, int M) {
if (N == 1) {
return 1;
}
if (M == 0) {
return 0;
}
if (dp[N][M] > 0) {
return dp[N][M];
}
long cnt = 0;
for (int k = 1; k < N; k++) {
long upper = L - (M - 1);
long unusedEdgeNum = k * (N - k) - 1;
long pow = modPow(upper, unusedEdgeNum) % MOD;
cnt += dp(k, M - 1) * dp(N - k, M) % MOD * pow;
cnt %= MOD;
}
dp[N][M] = (dp(N, M - 1) + cnt) % MOD;
return dp[N][M];
}
private long modPow(long x, long e) {
long ret = 1;
long cur = x;
while (e > 0) {
if (e % 2 == 1) {
ret = (ret * cur) % MOD;
}
cur = (cur * cur) % MOD;
e >>= 1;
}
return ret;
}
}