题目描述

$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$

样例数据

输入:

4 2 2

输出:

6

说明:

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