Description

n 块积木排成一排，需要给每块积木染色，颜色有m 种。请问有多少种方法，从第二块积木开始统计，恰有 p 块积木与前一块积木颜色不同？

Format

Input

三个整数分别表示 n,m,p

Output

输出满足条件的方案数模10^9+7的结果

Samples

4 2 2

6

设两种颜色分别为1,2 则有：1121,1211,1221,2122,2112,2212共计6种

Limitation

1s, 1024KiB for each test case.对于 100% 的数据，1≤n,m≤5000,1≤p<n