Description

n 块积木排成一排，需要给每块积木染色，颜色有 <math xmlns="http://www.w3.org/1998/Math/MathML">m 种。请问有多少种方法，从第二块积木开始统计，恰有 <math xmlns="http://www.w3.org/1998/Math/MathML">p 块积木与前一块积木颜色不同？

Input Format

三个整数分别表示 <math xmlns="http://www.w3.org/1998/Math/MathML">n,m,p

Output Format

输出满足条件的方案数模<math xmlns="http://www.w3.org/1998/Math/MathML">109+7的结果

4 2 2

6

Hint

• 对于 <math xmlns="http://www.w3.org/1998/Math/MathML">30% 的数据，<math xmlns="http://www.w3.org/1998/Math/MathML">1≤n,m≤10
• 对于 <math xmlns="http://www.w3.org/1998/Math/MathML">60% 的数据，<math xmlns="http://www.w3.org/1998/Math/MathML">1≤n,m≤500
• 对于 <math xmlns="http://www.w3.org/1998/Math/MathML">100% 的数据，<math xmlns="http://www.w3.org/1998/Math/MathML">1≤n,m≤5000,<math xmlns="http://www.w3.org/1998/Math/MathML">1≤p<n

Source

快速幂 数论 组合排列 上海市2023年1月赛