问题2966--难题(hard)

2966: 难题(hard)

时间限制: 1 Sec  内存限制: 512 MB
提交: 6  解决: 2
[提交] [状态] [讨论版] [命题人:]

题目描述

有一个n行m列共计n*m(1≤n,m≤〖10〗^5)个格子的网格图,给定正整数K(K≤〖10〗^9),你可以在每一个格子内填一个在[1,K]区间内的任意的正整数。对于一个填完数的网格图,定义数组A和B:A_i (i=1,2,…,n)为第i行的最大值,B_i (i=1,2,…,m)为第i列的最大值。
如果让你在格子内任意填数,你可以得到多少种不同的(A,B)?(A,B)与(A^',B')不同当且仅当存在i使得A_i≠A_i'或者存在i使得B_i≠B_i'。(即A中存在至少一个数不同或B中存在至少一个数不同即为两个方案互不相同)
输出答案模〖10〗^9+7。

输入

第一行一个正整数T,表示数据组数。
每组数据包含一行三个正整数n,m,K。

输出

输出一行答案,模〖10〗^9+7。

样例输入 Copy

2
2 3 2
41 42 2

样例输出 Copy

22
903408624

提示

来源/分类