解题思路：
要求一条直线分割矩阵时左右颜色数一样，那么就说明一个问题。
直线左右移动时是不会改变左右矩阵的颜色集合的。
所以说明：2~m-1列的颜色集一定属于第一列与第m列颜色集的交集。
而且第一列与第m列颜色集大小相等。
显然需要预处理n个点m种颜色的方案数，设为$g(i,j)$
这样，只需要确定第一列和最后一列颜色集，假设交集是$i$种颜色，
就可以算出中间的颜色方案数：$i^{n*(m-2)}$
假设两边颜色个数都是$j$（$j\ge i$）那么两边颜色的答案（$(g(n,j)j!)^2$）
这$i$种颜色共有$C_k^i$种选法，两边各$j$种颜色，且只有$i$种颜色相同的方案就是：
$\Large C_k^iC_{k-i}^{2(j-i)}C_{2(j-i)}^{j-i}$
那么答案就是
$\Large\sum\limits_{i=1}^{n}\sum\limits_{j=i}^{n}C_k^iC_{k-i}^{2(j-i)}C_{2(j-i)}^{j-i}{(g(n,j)j!)^2}{i^{n(m-2)}}$
代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
typedef long long lnt;
const lnt mod=;
lnt g[][];
lnt fac[];
lnt inv[];
int n,m,k;
lnt ans;
lnt ksm(lnt a,lnt b)
{
lnt ans=;
while(b)
{
if(b&)ans=ans*a%mod;
a=a*a%mod;
b=b/;
}
return ans;
}
lnt C(int x,int y)
{
if(y>x)return ;
return fac[x]*inv[y]%mod*inv[x-y]%mod;
}
lnt squ(lnt x)
{
return x*x%mod;
}
int main()
{
g[][]=;
fac[]=inv[]=fac[]=inv[]=;
for(int i=;i<=;i++)
{
fac[i]=(fac[i-]*i)%mod;
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
}
for(int i=;i<=;i++)inv[i]=inv[i]*inv[i-]%mod;
scanf("%d%d%d",&n,&m,&k);
if(m==)
{
printf("%I64d\n",ksm(k,n));
return ;
}
for(int i=;i<=n;i++)
{
for(int j=;j<=i&&j<=k;j++)
{
g[i][j]=(g[i-][j-]+g[i-][j]*j)%mod;
}
}
for(int i=;i<=n;i++)
{
lnt tmp=ksm(i,n*(m-))*C(k,i)%mod;
for(int j=i;j<=n;j++)
{
ans=(ans+tmp*C(k-i,(j-i)*)%mod*C((j-i)*,j-i)%mod*squ(g[n][j]*fac[j]%mod)%mod)%mod;
}
}
printf("%I64d\n",(ans%mod+mod)%mod);
return ;
}