Problem: Sunuke came up with a pun called "s de t t", but forgot it. Sunuke remembers the following.

* The length of s is N.
* The length of t is M.
* t is a substring of s. (There is a part of consecutive M characters of s that matches t.)



Divide the number of possible combinations as (s, t) by 1,000,000,007 to find the remainder. However, it is assumed that there are A types of characters.

Constraints

* 1 ≤ N ≤ 200
* 1 ≤ M ≤ 50
* M ≤ N
* 1 ≤ A ≤ 1000

Input


N M A


Output

Divide the number of character string pairs (s, t) that satisfy the condition by 1,000,000,007 and output the remainder.

Examples

Input

3 2 2


Output

14


Input

200 50 1000


Output

678200960

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 1000000007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
vector<vector<int> >pat[55];
vector<vector<int> >rec(int num){
	if(num <= 1){
		vector<vector<int> >ret;
		ret.pb(vector<int>());
		return pat[num] = ret;
	}
	if(pat[num].size()) return pat[num];
	pat[num].pb(vector<int>());
	for(int i=1;i<num;i++){
		vector<int>hoge;
		int zan = num;
		for(int j=i;(j == i || zan >= 2*i);j+=i){
			hoge.pb(j);
			zan -= i;
		}
		vector<vector<int> >pl = rec(zan);
		for(int j=0;j<pl.size();j++){
			vector<int>vi = hoge;
			for(int k=0;k<pl[j].size();k++) vi.pb(hoge[hoge.size()-1]+pl[j][k]);
			pat[num].pb(vi);
		}
	}
	return pat[num];
}
int s,t,n;
int dp[(1<<15)];
bitset<64>ok[(1<<15)];
struct UF{
	int par[55],ran[55];
	void init(){ for(int i=0;i<55;i++) par[i] = i; }
	int find(int x){ if(x == par[x]) return x; else return par[x] = find(par[x]); }
	void unite(int x,int y){
		x = find(x); y = find(y); if(x==y) return;
		if(ran[x] < ran[y]) par[x] = y;
		else{
			par[y] = x;
			if(ran[x] == ran[y]) ran[x]++;
		}
	}
	bool same(int x,int y){ return find(x)==find(y); }
}uf[(1<<15)];
bool cmp(const vector<int>& a,const vector<int>& b){
	return a.size() > b.size();
}
ll DP[205][2];
int main(){
	cin>>s>>t>>n;
	rec(t);
	sort(pat[t].begin(),pat[t].end(),cmp);
	for(int i=0;i<pat[t].size();i++){
		uf[i].init();
		for(int j=0;j<pat[t][i].size();j++){
			ok[i][pat[t][i][j]] = 1;
			int a = pat[t][i][j];
			assert(1<=a && a<t);
			for(int k=0;k+a<t;k++) uf[i].unite(k,k+a);
		}
		ll x = 1;
		for(int k=0;k<t;k++){
			if(uf[i].find(k) == k){
				x = x*1LL*n%mod;
			}
		}
		dp[i] = int(x);
		for(int j=0;j<i;j++){
			if((ok[j]&ok[i]) == ok[i]){
				dp[i] -= dp[j];
				if(dp[i] < 0) dp[i] += mod;
			}
		}
	}
	ll ans = 0;
	for(int i=0;i<pat[t].size();i++){
		for(int j=0;j<=s;j++) DP[j][0] = DP[j][1] = 0;
		DP[0][0] = 1;
		ll cur[2] = {};
		cur[0] = 1;
		ll res = 0;
		for(int j=1;j<=s-t+1;j++){
			for(int k=0;k<2;k++){
				DP[j][k] += cur[1-k];
				for(int a=0;a<pat[t][i].size();a++){
					if(j-pat[t][i][a] <= 0) break;
					DP[j][k] += DP[j-pat[t][i][a]][1-k];
				}
				DP[j][k] %= mod;
			}
			cur[0] = cur[0]*1LL*n%mod;
			cur[1] = cur[1]*1LL*n%mod;
			if(j>=t){
				cur[0] = (cur[0]+DP[j-t+1][0])%mod;
				cur[1] = (cur[1]+DP[j-t+1][1])%mod;
			}
		}
		ll tg = 1;
		for(int j=s-t+1;j>=1;j--){
			res += DP[j][1] * tg % mod;
			res -= DP[j][0] * tg % mod;
			tg = tg*1LL*n%mod;
		}
		res %= mod;
		ans += dp[i]*res%mod;
	}
	cout << (ans%mod+mod)%mod << endl;
}