Description：

给一个 $n\times m$ 的网格和 $k$ 种颜色，求每行每列每种颜色都至少染了一格的方案数。

$1\leqslant n,m,c\leqslant400$

Solution：

直接容斥，枚举至多染了 $i$ 行 $j$ 列 $k$ 个颜色： $$ ans=\sum_{i=0}^n\sum_{j=0}^m\sum_{k=0}^c\binom ni\binom mj\binom ck(-1)^{n+m+c-i-j-k}(k+1)^{ij} $$ 肯定是要交换求和号，但是把 $k$ 交换到最后不太可做，正解是把 $j$ 交换到最后： $$ ans=\sum_{i=0}^n\sum_{k=0}^c\binom ij\binom ck(-1)^{n+m+c-i-k}\sum_{j=0}^m\binom mj(-1)^{j}(k+1)^{ij} $$ 观察最后一个求和号： $$ \sum_{j=0}^m\binom mj(-1)^j(k+1)^{ij}=\sum_{j=0}^m\binom mj\Bigl((-1)(k+1)^i\Bigr)^j=\Bigl((-1)(k+1)^i+1\Bigr)^m $$ 那么： $$ ans=\sum_{i=0}^n\sum_{k=0}^c\binom ij\binom ck(-1)^{n+m+c-i-k}\Bigl((-1)(k+1)^i+1\Bigr)^m $$ 于是就可以 $O(n\log n)$ 求了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;register char c = getchar();

	while(!isdigit(c)){if(c == '-')f = -1;c = getchar();}

	while(isdigit(c))res = (res << 1) + (res << 3) + c - '0',c = getchar();

	return res * f;

}

int n,m,c;

#define MOD 1000000007

int power(int a,int b)

{

	int res = 1;

	while(b > 0)

	{

		if(b & 1)res = 1ll * res * a % MOD;

		a = 1ll * a * a % MOD;

		b = b >> 1;

	}

	return res;

}

#define MAXN 410

#define N 400

int fac[MAXN],inv[MAXN];

int C(int n,int m)

{

	return 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;

}

int main()

{

	scanf("%d%d%d",&n,&m,&c);

	fac[0] = 1;for(int i = 1;i <= N;++i)fac[i] = 1ll * fac[i - 1] * i % MOD;

	for(int i = 0;i <= N;++i)inv[i] = power(fac[i],MOD - 2);

	int ans = 0;

	for(int i = 0;i <= n;++i)

	{

		for(int k = 0;k <= c;++k)

		{

			ans = (ans + 1ll * C(n,i) * C(c,k) % MOD * power(MOD - 1,n + m + c + i + k) % MOD * power(1ll * (MOD - 1) % MOD * power(k + 1,i) % MOD + 1,m) % MOD) % MOD;

		}

	}

	cout << ans << endl;

	return 0;

}