题目描述
$n$ 块积木排成一排，需要给每块积木染色，颜色有 $m$ 种。请问有多少种方法，从第二块积木开始统计，恰有 $p$ 块积木与前一块积木颜色不同？
输入
三个整数分别表示 $n,m,p$
输出
输出满足条件的方案数模$10^9+7$的结果
样例输入输出
提示
- 对于 $30\%$ 的数据，$1 \leq n,m \leq 10$
- 对于 $60\%$ 的数据，$1 \leq n,m \leq 500$
- 对于 $100\%$ 的数据，$1 \leq n,m\leq 5000$,$1 \leq p \lt n$
样例1说明:设两种颜色分别为1,2
则有：1121,1211,1221,2122,2112,2212共计6种