One day, the math teacher give Tuhao a question:if you have 5 boxes in a line(every boxes are different) and you have 4 kinds of balls.you must put an ball in every box, and all balls can take unlimited. How many kinds of way of placing? Tuhao solve this problem easily.But he has another question to you.if we have N boxes, and we have m kind of balls, and you can't use all kinds of balls because Tuhao must have one kind ball at least to play with his partners...
Input
There will be multiple cases to consider. The first input will be a number T(0 < T ≤ 50) indicating how many cases with which you will deal. Following this number will be pairs of integers giving values for N and M, in that order. You are guaranteed that 1 ≤ N < 500, 1 ≤ M < 10, Each N M pair will occur on a line of its own. N and M will be separated by a single space.
Output
For each case display a line containing the case number (starting with 1 and increasing sequentially), and the kinds of way of placing. The desired format is illustrated in the sample shown below.(p.s. the answer should be module 200000007)
Sample Input
2 1 1 8 3
Sample Output
Case 1: 0 Case 2: 765
解析：定义F[I][J]表示前I个格子用了J种颜色，有如下方程：
F[I][J]=F[I-1][J-1]*(M-(J-1))+F[I-1][J]*J;
F[I-1][J-1]*(M-(J-1))：加上一种新的颜色的方案数,(M-(J-1))是剩下没用的颜色数
F[I-1][J]*J：从以前选了J种颜色中选一种、
开始F[I][1]=M；我为了避免处理麻烦，从I=2时开始操作；
这是未加工的部分
for (int i=1;i<=n;i++)
f[i][1]=1;
for (int i=2;i<=n;i++)
for (int j=1;j<=m;j++)
f[i][j]=(f[i-1][j]*j+f[i-1][j-1]*(m-j+1))%maxn;
int ans=0;
for (int i=1;i<m;i++)
ans=(ans+f[n][i])%maxn;
printf("%d ",ans*m%maxn);
}
return 0;
}