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>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
template<class S,class T> ostream& operator<<(ostream& o,const pair<S,T> &p){return o<<"("<<p.fs<<","<<p.sc<<")";}
template<class T> ostream& operator<<(ostream& o,const vector<T> &vc){o<<"sz = "<<vc.size()<<endl<<"[";for(const T& v:vc) o<<v<<",";o<<"]";return o;}
struct UnionFind{
	int par[51];
	void init(int N){rep(i,N) par[i]=i;}
	int find(int x){
		if(x==par[x]) return x;
		return par[x]=find(par[x]);
	}
	bool same(int x,int y){return find(x)==find(y);}
	void unite(int x,int y){
		x=find(x),y=find(y);
		par[x]=y;
	}
}UF;
typedef long long ll;
ll N,M,A,n[2249],mod=1e9+7;
ll dp[200][200];
void add(ll &x,ll y){
	x+=y;
	x%=mod;
}
inline ll B(int x){return 1LL<<x;}
bool B(ll x,int i){return (x>>i)&1;}
bool is_pset(ll b){
	UF.init(M);
	rep(i,M) if((b>>i)&1){
		rep(j,M-i) UF.unite(j,j+i);
	}
	ll x=0;
	rep1(i,M-1){
		bool ok=1;
		rep(j,M-i) if(!UF.same(j,j+i)) ok=0;
		if(ok) x|=B(i);
	}
	return b==x;
}
int dim(ll b){
	UF.init(M);
	rep(i,M) if((b>>i)&1){
		rep(j,M-i) UF.unite(j,j+i);
	}
	int d=0;
	rep(i,M) if(i==UF.find(i)) d++;
	return d;
}
vector<ll> vc;
void enum_pset(int L,ll b){
	if(L==0){
		if(is_pset(b)) vc.pb(b);
		return;
	}
	rep1(p,L){
		if(p<=L/2){
			ll nb=b;
			for(int k=p;k<L;k+=p) nb|=B(k+M-L);
			enum_pset(L%p+p,nb);
		}else{
			ll nb=b;
			for(int k=p;k<L;k+=p) nb|=B(k+M-L);
			enum_pset(L-p,nb);
		}
	}
}
ll calc(ll x){
	rep(i,N) rep(j,N) dp[i][j]=0;
	dp[0][0]=1;
	rep(i,N-M) dp[i+1][i+1]=dp[i][i]*A%mod;

	rep(i,N-1) rep(j,N) if(dp[i][j]!=0){
		if(i+1+M<=N && (i+1>=j+M || B(x,i+1-j)) ){
			add(dp[i+1][i+1],-dp[i][j]);
		}
		if(i+1>=j+M) add(dp[i+1][j],dp[i][j]*A);
		else add(dp[i+1][j],dp[i][j]);
	}
	ll ret=0;
	rep(j,N) add(ret,dp[N-1][j]);
	return ret;
}

int main(){
	cin>>N>>M>>A;
	enum_pset(M,0);
	sort(all(vc));
	vc.erase(unique(vc.begin(),vc.end()),vc.end());
	int K=vc.size();
	reverse(all(vc));
	rep(i,K){
		int d=dim(vc[i]);
		n[i]=1;
		rep(j,d) n[i]=n[i]*A%mod;
	}
	ll ans=0;
	rep(i,K){
		ll tmp=calc(vc[i]);
		rep(j,i) if((vc[i]&vc[j])==vc[i]) add(n[i],-n[j]);
		add(ans,n[i]*tmp);
	}
	cout<<(ans+mod)%mod<<endl;
}