Substring Pairs

時間制限 : 2 sec, メモリ制限 : 262144 KB

すぬけ君は,"st t" というダジャレを思いついたが,忘れてしまった.すぬけ君は以下のことを覚えている.

  • s の長さは N である.
  • t の長さは M である.
  • ts の部分文字列である.(s の連続する M 文字で t と一致している部分が存在する.)

(s, t) として考えられる組み合わせの個数を 1,000,000,007 で割ったあまりを求めよ.ただし,文字は A 種類存在するものとする.

Constraints

  • 1 ≤ N ≤ 200
  • 1 ≤ M ≤ 50
  • MN
  • 1 ≤ A ≤ 1000

Input

N M A

Output

条件を満たす文字列の組 (s, t) の個数を 1,000,000,007 で割ったあまりを出力せよ.

Sample Input 1

3 2 2

Sample Output 1

14

Sample Input 2

200 50 1000

Sample Output 2

678200960

Source: ACM-ICPC Japan Alumni Group Summer Camp 2014 , Day 2, Tokyo, Japan, 2014-09-13
http://acm-icpc.aitea.net/
http://jag2014summer-day2.contest.atcoder.jp/