#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 5 , MOD = 1e9 + 7 , INV2 = MOD / 2 + 1;
int n , m , k , pw[N] , ipw[N];
namespace BF
{
	const int N = 10;
	int s1[N] , s2[N] , cnt[N] , nxt[N] , res[N];
	int Solve()
	{
		int ans = 0;
		for(int t = 0 ; t < pw[m] ; t++)
		{
			memset(cnt , 0 , sizeof cnt);
			bool fail = 0;
			for(int i = 0 ; i < m ; i++)
			{
				s2[i] = t / pw[i] % k;
				if(++cnt[s2[i]] > 2)fail = 1;
			}
			if(!fail)
			{

				// for(int i = 0 ; i < m ; i++)
				// 	cerr << s2[i] << ',';
				// cerr << "\n";
				int border = 0;
				for(int i = 1 ; i <= m / 2 ; i++)
				{
					bool ok = 1;
					for(int j = 0 ; j < i && ok ; j++)
						if(s2[j] != s2[m  - i + j])ok = 0;
					if(ok)border = i;
				}
				// cerr << "border = " << border << "\n";
				for(int s = 0 ; s < pw[n] ; s++)
				{
					for(int i = 0 ; i < n ; i++)
						s1[i] = s / pw[i] % k;
					for(int i = 0 ; i <= n - m ; i++)
					{
						bool ok = 1;
						for(int j = 0 ; j < m && ok ; j++)
							if(s1[i + j] != s2[j])ok = 0;
						if(ok)
						{
							ans++ , res[border]++;
							// cerr << "\t" << i << "  ";
							// for(int i = 0 ; i < n ; i++)
							// 	cerr << s1[i] << ',';
							// cerr << "\n";
							i += m - 1;
						}
					}
				}
			}
		}
		cout << ans << "\n";
		// for(int i = 0 ; i <= m / 2 ; i++)
		// 	cerr << res[i] << " \n"[i == m / 2];
		return 0;
	}
}
namespace NM
{
	const int M = 2005;
	int fac[M] , ifac[M] , ip2[M] , dk[M];
	int Qpow(ll x , ll p)
	{
		ll res = 1;
		x %= MOD , p %= MOD - 1;
		if(p < 0)p += MOD - 1;
		for(; p ; p >>= 1 , x = x * x % MOD) 
			if(p & 1)res = res * x % MOD;
		return res;
	}
	void Init(int n)
	{
		ip2[0] = fac[0] = ifac[0] = 1;
		for(int i = 1 ; i <= n ; i++)
			fac[i] = (ll)fac[i - 1] * i % MOD;
		ifac[n] = Qpow(fac[n] , MOD - 2);
		for(int i = n - 1 ; i >= 1 ; i--)
			ifac[i] = (ll)ifac[i + 1] * (i + 1) % MOD;
		for(int i = 1 ; i <= n ; i++)
			ip2[i] = (ll)ip2[i - 1] * INV2 % MOD;
	}
	int C(int n , int m)
	{
		if(n < m || m < 0)return 0;
		return (ll)fac[n] * ifac[m] % MOD * ifac[n - m] % MOD;
	}
	int F(int k , int m)
	{
		int ans = 0 , s = min(m / 2 , k) , dn = 1;
		for(int i = 0 ; i < m - s ; i++)dn = (ll)dn * (k - i) % MOD;
		for(int j = s ; j >= max(m - k , 0) ; j--)
		{
			ans = (ans + ((ll)dn * ip2[j] % MOD) * ((ll)ifac[j] * ifac[m - j * 2] % MOD)) % MOD;
			dn = (ll)dn * (k - m + j) % MOD;
		}
		ans = (ll)ans * fac[m] % MOD;
		return ans;
	}
	int Solve()
	{
		Init(m);
		int sum = 0 , ans = 0; 
		dk[0] = 1;
		for(int i = 1 ; i <= min(m / 2 , k) ; i++)
			dk[i] = (ll)dk[i - 1] * (k - i + 1) % MOD;
		ipw[0] = 1 , ipw[1] = Qpow(k , MOD - 2);
		for(int i = 2 ; i <= m ; i++)ipw[i] = (ll)ipw[i - 1] * ipw[1] % MOD;
		for(int len = min(m / 2 , k) ; len >= 0 ; len--)
		{
			int c = (ll)dk[len] * F(k - len , m - len * 2) % MOD;
			// cerr << "border len = " << len << " : " << c << "\n";
			if(!len)c = (c + MOD - sum) % MOD;
			else sum = (sum + c) % MOD;
			int res = 0;
			if(!len)res = ll(n - m + 1) * pw[n - m] % MOD;
			else
			{
				int kni = Qpow(k , n - m) , dt = Qpow(Qpow(k , (m - len)) , MOD - 2);
				for(int i = m , l = 2 ; i <= n ; i += m - len , l++ , kni = (ll)kni * dt % MOD) 
				{
					int t = 0 , tt = 0 , r = m - len;
					int p = ll(pw[r] - 1) * ipw[r] % MOD;
					// for(int j =  1 ; j <= n - i + 1 ; j++)
					// {
					// 	auto W = [&](int l)
					// 	{
					// 		if(l >= r)return (ll)p * pw[l] % MOD;
					// 		return (ll)pw[l];
					// 		// return (ll)(pw[min(r , l)] - (l >= r)) * pw[max(l - r , 0)] % MOD;
					// 	};
					// 	tt = (tt + (ll)W(j - 1) * W(n - i - j + 1)) % MOD;
					// }
					if(n - i + 1 >= 2 * r)
					{
						int p2 = (ll)p * p % MOD;
						t = (ll(n - i + 1 - r * 2) * p2 % MOD + ll(2 * r) * p % MOD) % MOD;
					}
					else
					{
						int L = max(0 , n - i - r + 1);
						int R = min(n - i + 2 , r + 1);
						t = (ll(R - L - 1) + ll(L + n - i + 2 - R) * p) % MOD;
						// cerr << "\t" << t << "\n";
					}
					t = (ll)t * kni % MOD;
					// cerr << t << ' ' << tt << " ; " << kni << " = " << Qpow(k , n - i) << " ; " << r << ';' << n - i + 1 << "\n";
					// if(i < n)
					// {
					// 	if(i < n - 1)t = (t + (n - i - 1) * ((ll)(k - 1) * (k - 1) % MOD) % MOD * pw[n - i - 2]) % MOD;
					// 	t = (t + 2ll * (k - 1) % MOD * pw[n - i - 1]) % MOD;
					// }
					// else t = 1;
					res = (res + (ll)(l >> 1) * t) % MOD; 
				}
			}
			// cerr << len << ":" << c << " * " << res << "\n";
			ans = (ans + (ll)res * c) % MOD;
		}
		cout << ans << "\n";
		return 0;
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0) , cout.tie(0);
	cin >> n >> m >> k;
	pw[0] = 1;
	for(int i = 1 ; i <= n ; i++)
		pw[i] = (ll)k * pw[i - 1] % MOD;
	// if(n <= 5 && m <= 5 && k <= 3)
	// BF::Solve();
	NM::Solve();
	return 0;
}