題目大意：
用k種顏色塗 n*m 的矩形，要求 如果 1~i 和 i+1~m 所用的顏色種類一樣多，不要求顏色一樣、
思路：
可以推出 第一列和第m列所用的顏色數量是一樣的。
證明 ：如果a[1~1]=i a[m~m]=j (i
那麼a[1~1]=i
然後中間的m-2列 是不能出現新顏色的。也就是必須是第一列和第m列的顏色不然會導致兩邊不相等了。
用dp[i] 表示用i種顏色且必須是i種顏色塗在n個格子上的方式。
那麼 dp[i] = i^n-segma(C(i,j)*dp[j]) 1<=j
然後我們開始處理，
當m==1的時候 就是k^n
當m==2的時候 左邊i種 右邊 i種 就是 （C（k，i）*dp[i]）^2...
當m==3的時候
要枚舉相同的顏色的數量i 和不同的顏色的數量j
第一列在k個裡選i個 然後在k-i個裡選擇選擇j個 第m列則要在k-i-j裡再選j個
然後再塗上去 就是乘以 dp[i+j]...
#include
#include
#include
#include
typedef long long LL;
using namespace std;
const LL mod=1000000007;
LL fac[1000005]={1},rev[1000005]={1};
LL dp[1005];
LL pow_mod(LL a,LL i,LL n)
{
if(i==0)return 1%n;
LL temp=pow_mod(a,i>>1,n);
temp=temp*temp%n;
if(i&1)temp=temp*a%n;
return temp;
}
void init()
{
for(int i=1;i<=1000000;i++)
fac[i]=fac[i-1]*i%mod,rev[i]=pow_mod(fac[i],mod-2,mod);
}
LL C(int n,int m)
{
return (fac[n]*rev[m]%mod)*rev[n-m]%mod;
}
int main()
{
init();
int n,m,k;
scanf("%d%d%d",&n,&m,&k);
if(m==1)
{
printf("%I64d\n",pow_mod(k,n,mod));
return 0;
}
for(int i=1;i<=n && i<=k;i++)
{
dp[i]=pow_mod(i,n,mod);
for(int j=1;j
