相当惊奇，开 O2 全 T，不开最长 $12\text{ms}$。

#include<cstdio>
using namespace std;
int n,m,cl;
const int mod = 1e9 + 7;
int c[409][409];
void init(){
	c[0][0] = 1;
	for(int i = 1; i <= 400; i ++){
		c[i][0] = 1;
		for(int j = 1; j <= 400; j ++){
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
		}
	}
}
int f_m(int a,int b){
	if(a == 0)
		return 0; 
	if(b == 0)
		return 1;
	int t = f_m(a,b >> 1);
	if(b & 1){
		return 1ll * t * t % mod * a % mod;
	}
	else{
		return 1ll * t * t % mod;
	}
}
//1.每行至少一个
//2.每列至少一个
//3.每种颜色至少一个 
int f0(int n,int m,int cl){//1
	int o = (mod + f_m((cl + 1) % mod,m) - 1) % mod;
	return f_m(o,n);
}
int f1(int n,int m,int cl){//1 + 2
	int ans = 0;
	for(int i = m,t = 1; i >= 0; i --,t *= -1){
		ans = ((long long)mod + ans + 1ll * f0(n,i,cl) * c[m][i] % mod * t) % mod;
	}
	return ans;
}
int f2(int n,int m,int cl){//1 + 2 + 3
	int ans = 0;
	for(int i = cl,t = 1; i >= 0; i --,t *= -1){
		ans = ((long long)mod + ans + 1ll * f1(n,m,i) * c[cl][i] % mod * t) % mod;
	}
}
int main(){
	init();
	scanf("%d %d %d",&n,&m,&cl);
	printf("%d\n",f2(n,m,cl));
	return 0;
}