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

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

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

Constraints

• 1 ≤ N ≤ 200
• 1 ≤ M ≤ 50
• M ≤ N
• 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