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
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
// Jan Burdzicki
#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 3e3 + 5;
const int MOD = 1e9 + 7;

vector <long long> potegi(MAX_N);

long long przypadek_2()
{
	long long wynik = potegi[1];

	return wynik;
}

long long przypadek_3()
{
	long long wynik = potegi[2];

	return wynik;
}

long long przypadek_4()
{
	long long wynik = (((potegi[3] + potegi[2] - potegi[1]) % MOD) + MOD) % MOD;

	return wynik;
}

long long przypadek_5()
{
	long long wynik = (((potegi[4] + 2 * potegi[3] - 2 * potegi[2]) % MOD) + MOD) % MOD;

	return wynik;
}

long long przypadek_6()
{
	long long wynik = (((potegi[5] + 3 * potegi[4] - 2 * potegi[3] - 4 * potegi[2] + 3 * potegi[1]) % MOD) + MOD) % MOD;

	return wynik;
}

long long przypadek_7()
{
	long long wynik = (((potegi[6] + 4 * potegi[5] - potegi[4] - 12 * potegi[3] + 9 * potegi[2]) % MOD) + MOD) % MOD;

	return wynik;
}

void preprocessing(int ilosc_gatunkow)
{
	potegi[0] = 1;

	for(int i = 1; i < MAX_N; i++)
	{
		potegi[i] = (potegi[i - 1] * ilosc_gatunkow) % MOD;
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	int n, ilosc_gatunkow;
	cin >> n >> ilosc_gatunkow;

	preprocessing(ilosc_gatunkow);

	if(n <= 7)
	{
		// Udalo sie znalezc pierwsze 7 wielomianow

		if(n == 1)
		{
			cout << "0\n";
		}

		if(n == 2)
		{
			cout << przypadek_2() << "\n";
		}

		if(n == 3)
		{
			cout << przypadek_3() << "\n";
		}

		if(n == 4)
		{
			cout << przypadek_4() << "\n";
		}

		if(n == 5)
		{
			cout << przypadek_5() << "\n";
		}

		if(n == 6)
		{
			cout << przypadek_6() << "\n";
		}

		if(n == 7)
		{
			cout << przypadek_7() << "\n";
		}
	}

	else
	{
		// Nie udalo sie znalezc przyksztalcenia obecnego wielomianu w nastepny
		// Ani tez wzoru ogolnego

		// Ale wielomian[n] = wielomian[n - 1] * (x + 1) + r
		// Reszta r jest stosunkowo niewielka

		long long wynik = przypadek_7();

		for(int i = 0; i < n - 7; i++)
		{
			wynik *= (ilosc_gatunkow + 1);

			wynik %= MOD;
		}

		cout << wynik << "\n";
	}

	return 0;
}