题目链接：
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 imes 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)}gcdot 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)}gcdot 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 imes M$ 个好格子，因此 $sum_{g=0}^{min(N,M)}gcdot 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+7; int n,m,k; ll fpow(ll a,ll n) { ll res=1,base=a%mod; while(n) { if(n&1) res*=base, res%=mod; base*=base, base%=mod; n>>=1; } return res%mod; } int main() { int T; cin>>T; for(int kase=1;kase<=T;kase++) { cin>>n>>m>>k; ll ans=0; for(int i=2;i<=k;i++) { ans+=fpow(i-1,n+m-2)*fpow(k,(n-1)*(m-1))%mod; ans%=mod; } ans*=(n*m)%mod, ans%=mod; ans+=fpow(k,n*m), ans%=mod; printf("Case #%d: %lld ",kase,ans); } }