前置知识：经典容斥，可以在我的 blog 里了解一下

容斥套容斥。

我们考虑一个一个地通过容斥把这些条件去掉，先令元素是所有染色方案，第 $i$ 个颜色的出现次数是 $c_i$，条件集合是 $\{c_1=0,c_2=0,\dots\}$ 套用容斥模型消掉最后一个条件，注意到这些颜色的地位是等价的，我们枚举条件集合大小化简式子，答案就是

$$\begin{aligned} &\sum_{S\subseteq U}(-1)^{|S|}f(S)\\ =&\sum_{i=0}^c\binom{c}{i}(-1)^{|S|}s(c-i)\\ \end{aligned}$$

其中 $s(c)$ 是只用 $\leq c$ 种颜色不考虑第颜色条件的涂色方案数。

接下来再容斥掉行列限制，若第 $i$ 行全不染那么 $q_i=0$，令条件集合是 $\{q_1=0,q_2=0,\dots\}$，每一行的地位也是等价的，我们得到

$$\begin{aligned} s(c)=&\sum_{S\subseteq U}(-1)^{|S|}f(S)\\ =&\sum_{i=0}^n\binom{n}{i}(-1)^is'(c,n-i)\\ \end{aligned}$$

其中 $s'(n,i)$ 是只用 $\leq n$ 种颜色，假设地图只有 $i$ 行后不考虑行和颜色条件的涂色方案数，只需考虑不允许有空列，剩下随便填，显然就是

$$s(c,i)=\bigg((c+1)^{i}-1\bigg)^m$$

（考虑先填出一列合法的，然后再拼出 $m$ 列）

时间复杂度 $O(nc\log m)$。

# include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e5 + 225;
const ll Mod = 1e9 + 7;

int n , m , c;

ll Pow( ll x , ll y ){
  ll res = 1;
  while( y ){
    if( y & 1 ) res = res * x % Mod;
	x = x * x % Mod , y >>= 1;
  }
  return res;
}

ll f[ N ] , invf[ N ] , g[ N ];

ll Binom( int p , int q ){ return f[ p ] * invf[ q ] % Mod * invf[ p - q ] % Mod; }

ll G( int p , int q ){ return Pow( ( Pow( p + 1 , q ) - 1 + Mod ) % Mod , m ); }

ll F( int p ){
  ll res = 0;
  for( int i = 0 ; i <= n ; i ++ ) res = ( res + ( ( i & 1 ) ? Mod - 1 : 1 ) * Binom( n , i ) % Mod * G( p , n - i ) % Mod ) % Mod;
  return res;
}

int main(){
  scanf( "%d%d%d" , & n , & m , & c );
  f[ 0 ] = invf[ 0 ] = 1;
  int wq = max( max( n , m ) , c );
  for( int i = 1 ; i <= wq ; i ++ ) f[ i ] = f[ i - 1 ] * i % Mod;
  invf[ wq ] = Pow( f[ wq ] , Mod - 2 );
  for( int i = wq - 1 ; i >= 1 ; i -- ) invf[ i ] = invf[ i + 1 ] * ( i + 1 ) % Mod;
  ll ans = 0;
  for( int i = 0 ; i <= c ; i ++ ) ans = ( ans + ( ( i & 1 ) ? Mod - 1 : 1 ) * Binom( c , i ) % Mod * F( c - i ) ) % Mod;
  printf( "%lld\n" , ans );
  return 0;
}