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
46
47
48
49
50
51
52
53
54
55
56
#include <vector>
#include <array>
#include <cinttypes>
#include <cstring>
#include <climits>
#include<iostream>
using namespace std;
namespace wzor
{
	const int64_t MMOD = 1'000'000'007;
}
int64_t solve_wzor(int64_t n, int64_t m)
{
	//Śmieszna historia, czytając to zadanie pomyliłem się i myślałem że na wejściu mamy 
	//podane jeszcze k, oznaczające ilość dnii po których Bajtazar ma skończyć, a Bajtazar musi skończyć dzień przy pierwszej możliwej okazji
	//Co ciekawe takie zadanie da się rozwiązać przy lepszym modulo, bądź trochę mniejszym wejściu
	//bo stała, ale działałoby w n^2 log n
	using namespace wzor;
	vector<vector<vector<int64_t>>> dp(n + 1, vector<vector<int64_t>>(n + 1, vector<int64_t>(2, 0)));
	//dp[number of position][number of used colors][is color trail]
	dp[1][1][0] = m;
	for(int64_t i = 2; i <= n - 1; ++i)
	{
		for(int64_t j = 1; j <= n; ++j)
		{
			dp[i][j][0] = dp[i - 1][j][0] * (m - j) + dp[i - 1][j - 1][1] * (m - j + 1);
			dp[i][j][0] %= MMOD;
			dp[i][j][1] = dp[i - 1][j][1] * j + dp[i - 1][j][0] * j;
			dp[i][j][1] %= MMOD;
		}
	}
	/*for(int i = 1; i <= n; ++i)
	{
		cout << i << ": ";
		for(int j = 1; j <= n; ++j)
		{
			cout << dp[i][j][0] << ' ' << dp[i][j][1] << " | ";
		}
		cout << '\n';
	}*/
	int64_t ans = 0;
	for(int i = 1; i <= n; ++i)
	{
		ans += (dp[n - 1][i][0] + dp[n - 1][i][1]) * i;
		ans %= MMOD;
	}
	return ans;
}
#include <iostream>

int main()
{
	int a, b;
	std::cin >> a >> b;
	std::cout << solve_wzor(a, b);
}