题解来自：
https://blog.csdn.net/infinity_edge/article/details/79090391
https://blog.csdn.net/martayang/article/details/54862753
题目链接：
https://vjudge.net/problem/UVALive-7904
https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=5926
题意：有一个 N行 M 列的矩阵，每一个格子是 [1,k]之间的一个整数。
定义一个格子是吼的，当且仅当该格子的值严格大于与其同行同列的所有格子种的值。定义 Ag为恰好有 g个吼的格子的互不相同的矩阵数目，求：
解析：
先把式子拆一下：
后者为所有矩阵的数目。
前者可以看成所有的矩阵的吼的格子的数目之和。
如果一个格子是吼的，那么该行该列所有的数都要严格小于该格子中的数。剩余 N?1 行 M?1 列的格子可以随便填，那么我们枚举这个数就可以了。
最后的答案为：
另一个思路：
这题乍一看需要用组合数学 容斥原理计算A-g，但是这样做比较麻烦复杂。但其实这题是(g+1)的套路。。。简便做法是观察整体，把问题转化成每个位置是great格子对最终答案的贡献和，这样就绕开了A-g的计算。
首先，考虑整体的填法：K^(M×N)——这个是容易计算的，那么我们先企图用整体填法数化简待求式！我们发现将待求式展开，后面的ΣA-g的和便是整体的填法数。（一般都需要先拿整体化简一把！）
于是现在只需着手计算Σg*A-g，这个就用贡献和的思想转化，因为有g个great格的填法数乘了个g相当于摊到了这g个位置上，也就是说每个great格独立了，也即每一个格是great格对Σg*A-g贡献=使这个格是great的所有填法总数：
Contrib=Σ（i=1到i=K-1）i^(N-1+M-1)×K^[(N-1)×(M-1)] （转化为贡献和，有点智力题的感觉orz..）
这里注意一点：以上公式没有考虑n=m=1的情况，因为这时填1也算是great格（而以上公式从填2开始考虑的）
从而最后：ans=Contrib×N×M+K^(M×N)
代码：
#include <bits/stdc++.h>
using namespace std;
#define mod 1000000007
typedef long long ll;
inline ll fpow(ll n,ll k)
{ll res=1;while(k>0){if(k&1)res=res*n%mod;n=n*n%mod;k>>=1;}return res;
}
inline ll solve(ll k,ll p)
{ll res=0;for(ll i=1;i<=k-1;i++){res+=fpow(i,p);res%=mod;}return res;
}
int N,M,K,T,cas;
int main()
{scanf("%d",&T);while(T--){scanf("%d%d%d",&N,&M,&K);cas++;ll ans=0;ans=solve(K,N+M-2);ans*=fpow(K,N*M-N-M+1);ans%=mod;ans*=N*M;ans%=mod;ans+=fpow(K,N*M);ans%=mod;printf("Case #%d: %lld\n",cas,ans);}return 0;
}