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
#include <iostream>

using namespace std ;

int main() {
	int ilosc; long long rodzaje; long long potega; long long sumka = 0;
	cin >> ilosc >> rodzaje;
	potega = rodzaje;
	long long potegi[ilosc]; long long fajne_sumki_tab [ilosc+1];
	potegi[0] = 1; fajne_sumki_tab[0] = 1;
	for(int i = 1; i < ilosc; i++)
	{
		potegi[i] = (potegi[i-1]*rodzaje)%1000000007;
		fajne_sumki_tab[i] = 0;
	}
	fajne_sumki_tab[2] = rodzaje;
	fajne_sumki_tab[3] = (rodzaje*rodzaje)%1000000007;
	fajne_sumki_tab[4] =  ((fajne_sumki_tab[3]*rodzaje)%1000000007+rodzaje*(rodzaje-1))%1000000007;
	for(int j = 5; j <= ilosc;j++)
	{
		sumka = 0;
		for( int i = j-4; i>=0;i--)
		{
			long long pomoc = (fajne_sumki_tab[j-4-i]*potegi[i])%1000000007;
			pomoc = (pomoc*(i+1))%1000000007;
			sumka = (sumka+pomoc)%1000000007;
		}
		sumka = (((sumka*rodzaje)%1000000007)*(rodzaje-1)%1000000007);
		long long wynik = 0;
		wynik = (potegi[j-1]+sumka)%1000000007;
		fajne_sumki_tab[j] = wynik;
	}
	cout << endl;

	
	if(ilosc==1)
	{
		cout << 0;
	}
	else if (ilosc==2)
	{
		cout << rodzaje;
	}
	else if(ilosc==3)
	{
		cout << (rodzaje*rodzaje)%1000000007;
	}
	else
	{
		cout << fajne_sumki_tab[ilosc];
	}
	return 0;
}