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
#include <cstdio>
#include <algorithm>
#define MAX_N 3100
#define MOD 1000000007
using namespace std;

long long unsigned cor[MAX_N][MAX_N], inCor[MAX_N][MAX_N];

int main() {
    int n, k;
    scanf("%d%d", &n, &k);

    cor[0][0] = 1;

    for (int dl = 1; dl <= n; dl++) {
        for (int i = 1; i <= min(dl, k); i++) {

            cor[dl][i] = (inCor[dl - 1][i] * i + cor[dl - 1][i] * i) % MOD;

            inCor[dl][i] = (inCor[dl - 1][i] * (k - i) + cor[dl - 1][i - 1] * (k - i + 1)) % MOD;
        }
    }

    long long unsigned res = 0;
    for (int i = 0; i <= n; i++) {
        res = (res + cor[n][i]) % MOD;
    }

    printf("%llu\n", res);
}