odd doctor 已更新

钞哥之家产继承

Time Limit
1s
Memory Limit
32768KB
Judge Program
Standard
Ratio(Solve/Submit)
100.00%(1/1)
Description:

在成年的那天,钞哥终于可以继承王氏家族的百亿家产了。但是王氏家族对继承者有很高的要求,设置了重重关卡。钞哥历经千辛万苦,终于到达了最后一关。出现在钞哥面前的是一个棋盘,但这个棋盘和规则有些奇特:

棋盘是由一个个格子组成的,共n行m列。每个格子里都可以放一个数字,但这个数字的大小必须在闭区间[1,k]的范围内。现在定义一个格子是完美的,当且仅当它严格大于它所在行及所在列的其他所有格子中的数字。设棋盘中恰好有g个完美格子的方案数为Ag,现在钞哥想要知道g从0到n*m,(g+1)*A[g]的和是多少(即(0+1)*A0+(1+1)*A1+...+(n*m+1)*Anm)。

钞哥陷入了僵局,但他有一次场外求助的机会,钞哥能不能继承百亿家产就靠你了,你能帮钞哥算出答案嘛。

Input:

先输入一个T,表示有T组数据。

每组数据输入三个整数n,m,k,分别表示有n行m列,每个格子中能填的数字范围为[1,k]。

1<=n,m,k<=100

Output:

上述表达式的值。这个数字可能过大,请输出答案关于(1e9+7)取模后的值。

Sample Input:
3
2 2 2
2 3 2
3 4 5
Sample Output:
24
88
487890625
Hint:

对于第一组样例,A0 = 10, A1 = 4, A2 = 2, A3 = A4 = 0, 因此答案是10+4×2+2×3 = 24。


Submit