Submission #994145

---

Source Code Expand

#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < n; i++)
#define PI       3.1415926535897932384626433832795028841971
#define INF      100000000
#define EPS      1e-10
#define MOD      1000000007
using namespace std;
typedef long long ll;
typedef pair<int,int> P;

ll n, m;
ll ans = 1;
ll dp[301][301];

ll justpow(ll x, ll y){
    ll ret = 1;
    while(y > 0){
        if(y&1) ret = ret*x%MOD;
        x = x*x%MOD;
        y /= 2;
    }
    return ret;
}

int main(){
    cin >> n >> m;
    if(n > m){
        cout << 0 << endl;
        return 0;
    }
    for(ll i = 1; i <= n-1; i++){
        ans = ans*i%MOD;
    }
    m -= n;
    for(ll i = 0; i <= m; i++) dp[0][i] = 1;
    for(ll i = 1; i < n; i++){
        for(ll u = 0; u <= m; u++){
            for(ll j = 0; j <= u; j++){
                if(i == n-1){
                    dp[i][u] = (dp[i][u]+justpow(i,u-j)*dp[i-1][j])%MOD;
                    continue;
                }
                dp[i][u] = (dp[i][u]+justpow(i+1,u-j)*dp[i-1][j])%MOD;
            }
        }
    }
    /*
    rep(i,n){
        rep(j,m+1){
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    */
    ll aans = dp[n-1][m];
    for(ll i = 0; i < m; i++){
        aans = (aans+dp[n-1][i]*justpow(n,m-i))%MOD;
    }
    cout << ans*aans%MOD << endl;
}

Submission Info

Judge Result