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
#include <cstdio>
#include <algorithm>
#define MOD 1000000007LL
#define MAKS 3010
using namespace std;
typedef long long int lld;

int f[MAKS][MAKS];
int g[MAKS][MAKS];

int main()
{
    int N,m;
    scanf("%d %d",&N,&m);
    if(N==1)
    {
        puts("0");
        return 0;
    }

    for(int k=0;k<=N;k++)f[0][k]=1;
    for(int k=0;k<=N;k++)g[0][k]=1;
    for(int n=1;n<=N-2;n++)
    {
        for(int k=N-1;k>=1;k--)
        {
            f[n][k]=(lld(min(k,m))*lld(g[n-1][k]))%MOD;
            f[n][k]=(lld(f[n][k]) + (lld(max(0,m-k))*lld(f[n-1][k]))%MOD)%MOD;
            g[n][k]=lld(min(k,m-1))*lld(g[n-1][k])%MOD;
            g[n][k]=(lld(g[n][k]) + (lld(max(0,m-k-1))*lld(f[n-1][k+1]))%MOD)%MOD;
        }
    }

    lld wsz=1;
    for(int i=0;i<N;i++)wsz=(wsz*lld(m))%MOD;
    //printf("wszystkich: %lld\n",wsz);
    int zlych;
    if(m==1)zlych=0;
    else zlych=(((lld(m)*lld(m-1))%MOD)*lld(f[N-2][1]))%MOD;
    //printf("zlych: %d\n",zlych);
    printf("%lld\n",(wsz+MOD-lld(zlych))%MOD);
}