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
#include <bits/stdc++.h>
using namespace std;
const int mod=10e9+7;

int pod_ciagi[3005];
long long int wynik=0;
vector <int> przypadek;
void zeruj()
{
	for(int i=0; i<=3000; i++)
	{
		pod_ciagi[i]=0;
	}
}

int poteguj(int l, int pot)
{
	long long int kwadrat=pot;
	long long int w=1;
	while(l>0)
	{
		if(l%2==1)
		{
			w=kwadrat*w;
			w=w%mod;
		}
		kwadrat=kwadrat*kwadrat;
		kwadrat=kwadrat%mod;
		l=l/2;
	}
	w=w%mod;
	return w;
}

long long int ile_dla_podciagu(int n, int k)
{
	long long int w;
	w=k*poteguj(k, n-2);
	w=w%mod;
	return w;
}

long long int policz_pod_przypadek(int k)
{
	int  pom;
	long long int w=1;
	for(int i=0; i<przypadek.size(); i++)
	{
		pom=przypadek[i]-pod_ciagi[i];
		pod_ciagi[i]++;
		if(pom<=1)
		{
			zeruj();
			return 0;
		}
		w=w*ile_dla_podciagu(pom, k);
		w=w%mod;
	}
	zeruj();
	return w;
}
void policz_sposoby(int n, int k)
{
	
	 int pom;
	 for(int i=2; i<=n; i++)
	 {
	 	pom=n-i;
		if(pom==0)
		{
			
			przypadek.push_back(i);
			wynik=wynik+policz_pod_przypadek(k);
		
			przypadek.clear();	
		}
		else
		{
			if(pom<0)
			{
				break;
			
				przypadek.clear();
			}
			else
			{
				pod_ciagi[i]++;
				przypadek.push_back(i);
				policz_sposoby(pom,k);
			}
		}
	 }
	 
}
int main()
{
	long long int sposoby=0;
	int n, k;
	cin>>n>>k;
	policz_sposoby(n, k);
	cout<<wynik<<endl;
	return 0;
}