1300: 积木染色（二）
Memory Limit：256 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：7
Solved：2
Description
$n$ 块积木排成一排，需要给每块积木染色，颜色有 $m$ 种。请问有多少种方法，从第二块积木开始统计，恰有 $p$ 块积木与前一块积木颜色不同？
Input
三个整数分别表示 $n,m,p$
Output
输出满足条件的方案数模 $10^9+7$ 的结果
Sample Input Copy
4 2 2Sample Output Copy
6HINT
样例说明：
设两种颜色分别为 $1,2$
则有：$1121,1211,1221,2122,2112,2212$ 共计 $6$ 种
数据范围：
- 对于 $30\%$ 的数据，$1≤n,m≤10$
- 对于 $60\%$ 的数据，$1≤n,m≤500$
- 对于 $100\%$ 的数据，$1≤n,m≤5000,1\le p \lt n $
设两种颜色分别为 $1,2$
则有：$1121,1211,1221,2122,2112,2212$ 共计 $6$ 种
数据范围：
- 对于 $30\%$ 的数据，$1≤n,m≤10$
- 对于 $60\%$ 的数据，$1≤n,m≤500$
- 对于 $100\%$ 的数据，$1≤n,m≤5000,1\le p \lt n $