题目链接：
http://codeforces.com/gym/101194/attachments
题意：
给出 $N$ 行 $M$ 列的网格，每个格子内可以填入 $[1,K]$ 内的任意整数。
如果某个格子，它是它所在行上严格最大的，同时也是所在列上严格最大的，则认为这个格子是好格子。
对于一个非负整数 $g$，可以有 $A_g$ 种填法使得网格内好格子数目正好为 $g$。
现在要求 $\sum_{g=0}^{NM}(g+1) A_g$，输出答案模 $1e9+7$ 后的结果。
题解：
首先，一个 $N \times M$ 的网格最多有 $\min(N,M)$ 个好格子，不可能更多了，因此 $\sum_{g=0}^{NM}(g+1) A_g = \sum_{g=0}^{\min(N,M)}(g+1) A_g$。
又 $\sum_{g=0}^{\min(N,M)}(g+1) A_g = \sum_{g=0}^{\min(N,M)}g\cdot A_g + \sum_{g=0}^{\min(N,M)} A_g$，
显然，$\sum_{g=0}^{\min(N,M)} A_g$ 即 $[1,K]$ 内的数无限制任意填入网格的所有填法数目 $K^{NM}$。
那么剩下来就是求 $\sum_{g=0}^{\min(N,M)}g\cdot A_g$：
单独考虑 $g \cdot A_g$ 的意义，现在我每一种能产生 $g$ 个好格子的方案，都要乘上一个 $g$。相当于对这 $g$ 个格子里的每个格子都累计上一个方案数 $A_g$。
那么换言之，$\sum_{g=0}^{\min(N,M)} A_g$ 就相当于，对每个格子让其成为好格子的方案数的累加。
而某一个格子，可以使得它成为好格子的填法有 $\sum_{i=2}^{K}(i-1)^{n-1+m-1}\cdot K^{(N-1)(M-1)}$ 种，
总共 $N \times M$ 个好格子，因此 $\sum_{g=0}^{\min(N,M)}g\cdot A_g = NM \sum_{i=2}^{K}(i-1)^{n-1+m-1}\cdot K^{(N-1)(M-1)}$。
综上，答案为 $\sum_{g=0}^{NM}(g+1) A_g = K^{NM} + NM \sum_{i=2}^{K}(i-1)^{n-1+m-1}\cdot K^{(N-1)(M-1)}$。
AC代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=1e9+;
int n,m,k;
ll fpow(ll a,ll n)
{
ll res=,base=a%mod;
while(n)
{
if(n&) res*=base, res%=mod;
base*=base, base%=mod;
n>>=;
}
return res%mod;
}
int main()
{
int T;
cin>>T;
for(int kase=;kase<=T;kase++)
{
cin>>n>>m>>k;
ll ans=;
for(int i=;i<=k;i++)
{
ans+=fpow(i-,n+m-)*fpow(k,(n-)*(m-))%mod;
ans%=mod;
}
ans*=(n*m)%mod, ans%=mod;
ans+=fpow(k,n*m), ans%=mod;
printf("Case #%d: %lld\n",kase,ans);
}
}