1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
#define ll long long int
using namespace std;

const int maxn=3005;
const ll mod=1e9+7;

ll dp[maxn];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    ll m;
    cin>>n>>m;

    if(n==1)
        cout<<"0";
    else if(n==2)
        cout<<m;
    else
    {
        dp[1]=0;
        dp[2]=m;
        for(int i=3; i<=n; ++i)
        {
            dp[i]=0;
            ll l=m;
            for(int j=i-1; j>=1; --j)
            {
                if(l<=0)
                    break;
                dp[i]+=(dp[j]*l)%mod;
                dp[i]%=mod;
                --l;
            }
        }
        cout<<dp[n];
    }
    return 0;
}

// dp[i] = m*dp[i-1] + (m-1)*dp[i-2] + (m-2)*dp[i-3] ...