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 <cstdio>
#include <cstdlib>

int eq[52];
int dsu[52];
int n;
int ways[2300][52], _[2300];
long long bit[2300];
int cnt;

int find(int x){return x == dsu[x] ? x : dsu[x] = find(dsu[x]);}

void dfs(int i, long long b){
  int j, k;
  int _dsu[52] = {};
  
  for (j = 1; j < i; j++)
    if (eq[j] == 0){
      for (k = 1; k <= j; k++)
	if (find(k) != find(n - j + k)) break;
      if (k > j) return;
    }

  if (i == n){
    cnt++;
    for (j = 1; j <= n; j++){
      ways[cnt][j] = eq[j];
      _[cnt] += (dsu[j] == j);
      bit[cnt] = b;
    }
    return;
  }

  for (j = 1; j <= n; j++) _dsu[j] = dsu[j];
  dfs(i + 1, b);
  eq[i] = 1;
  for (j = 1; j <= i; j++) dsu[find(j)] = find(n - i + j);
  dfs(i + 1, b | (1ll << i));
  for (j = 1; j <= n; j++) dsu[j] = _dsu[j];
  eq[i] = 0;
}

void prepare(){
  for (int i = 1; i <= n; i++) dsu[i] = i;
  dfs(1, 0);
}

const int ljz = 1000000007;
int Tm(int x, int y){long long a = x, b = y; return (a * b) % ljz;}
void MOD(int &x){if (x >= ljz) x -= ljz; if (x < 0) x += ljz;}

int m, a;
int pw[2322], gtf[2322];
int f[221][2];
int ans;
int G[2322];

void doit(int *w, int bh){
  int i, j, k;
  for (i = 1; i <= m + 1; i++) f[i][0] = f[i][1] = 0;
  for (i = 1; i <= m - n + 1; i++) f[i][1] = pw[i - 1];
  for (i = 1; i <= m - n + 1; i++)
    for (k = 0; k < 2; k++)
      if (f[i][k])
	for (j = i + 1; j <= m - n + 1; j++){
	  if (j - i < n){
	    if (w[n + i - j])
	      MOD(f[j][k ^ 1] += f[i][k]);
	  } else
	    MOD(f[j][k ^ 1] += Tm(f[i][k], pw[j - i - n]));
	}
  for (i = 1; i <= m - n + 1; i++){
    int q; MOD(q = f[i][1] - f[i][0]);
    MOD(ans += Tm(q, Tm(G[bh], pw[m - i - n + 1])));
  }
}

int main(){
  int i, j;
  scanf("%d %d %d", &m, &n, &a);
  for (i = pw[0] = 1; i <= m; i++) pw[i] = Tm(pw[i - 1], a);
  prepare();
  ans = 0;
  for (i = cnt; i; i--){
    G[i] = pw[_[i]];
    for (j = cnt; j > i; j--)
      if ((bit[i] & bit[j]) == bit[i])
	MOD(G[i] -= G[j]);
  }
  for (i = 1; i <= cnt; i++) doit(ways[i], i);
  printf("%d\n", ans);
  return 0;
}