題目描述

𝑛n?塊積木排成一排，需要給每塊積木染色，顏色有?𝑚m?種。請問有多少種方法，從第二塊積木開始統計，恰有?𝑝p?塊積木與前一塊積木顏色不同？

輸入格式

三個整數分別表示?𝑛,𝑚,𝑝n,m,p

輸出格式

輸出滿足條件的方案數模109+7109+7的結果

數據范圍

• 對于?30%30%?的數據，1≤𝑛,𝑚≤101≤n,m≤10
• 對于?60%60%?的數據，1≤𝑛,𝑚≤5001≤n,m≤500
• 對于?100%100%?的數據，1≤𝑛,𝑚≤50001≤n,m≤5000,1≤𝑝<𝑛1≤p<n

樣例數據

輸入:

4 2 2

輸出:

6

說明:

設兩種顏色分別為1,2
則有：1121,1211,1221,2122,2112,2212共計6種

詳見代碼:

#include<bits/stdc++.h>
using namespace std;
long long dp[5005][5005];
long long n,m,p,ans;
long long init(int x,int y)
{if (x==0||y==0) return 1;for (int i=1;i<=x;i++){for (int j=1;j<=y;j++){if (i==1){dp[i][j]=j;}else if (j==1){dp[i][j]=1;}else{dp[i][j]=(dp[i-1][j]+dp[i][j-1])%1000000007;}}}return dp[x][y];
}long long f(long long k,long long p)
{if(p==1){return k;}if(p%2==0){return (f(k,p/2))*(f(k,p/2))%1000000007;}else{return (((f(k,p/2))*(f(k,p/2))%1000000007)*k)%1000000007;}}
int main()
{cin>>n>>m>>p;ans=m*f(m-1,p)%1000000007;ans=(ans*init(n-p-1,p+1))%1000000007;cout<<ans<<endl;return 0;
}