시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB111100.000%

문제

Snuke came up with an integersing pair of strings (s, t), but forgot it. He remembers the following information:

  • The length of s is exactly N.
  • The length of t is exactly M.
  • t is a substring of s. (You can choose consecutive M characters from s that are the same as t.)

Compute the number of possible pairs of strings (s, t), modulo 109 + 7. Assume that the size of the alphabet is A.

입력

First line of the input consists of three integers N, M and A (1 ≤ N ≤ 200, 1 ≤ M ≤ 50, M ≤ N, 1 ≤ A ≤ 1000)

출력

Print the number of pairs of strings (s, t) that satisfy the conditions above, modulo 109 + 7.

예제 입력 1

3 2 2

예제 출력 1

14

예제 입력 2

200 50 1000

예제 출력 2

678200960