钞哥之家产继承

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

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

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

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

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

1<=n,m,k<=100

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

3
2 2 2
2 3 2
3 4 5

24
88
487890625

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