UVa 11806 Cheerleaders/反発原理

k個の石を求めてn*mのマトリックスの中でそれに第1行の最後の行の第1列の最後の列はすべて石があります
マイナスを考慮してすべてのマイナスが満たされていない場合を求める
反発の原理は全部で4つの集合A(第1行は石がない)B(最後の行は石がない)C(第1列は石がない)D(最後の列は石がない)
1つの集合を減算する2つの集合を加算する3つの集合を減算する4つの集合を加算する

#include <cstring>
#include <cstdio>

const int maxn = 510;
const int mod = 1000007;
int C[maxn][maxn];

int main()
{
	C[0][0] = 1;
	for(int i = 0; i <= 500; i++)
	{
		C[i][0] = C[i][i] = 1;
		for(int j = 1; j < i; j++)
			C[i][j] = (C[i-1][j] + C[i-1][j-1]) %mod;
	}
	int T;
	int cas = 1;
	scanf("%d", &T);
	while(T--)
	{
		int  n, m, k, sum = 0;
		scanf("%d %d %d", &n, &m, &k);
		for(int s = 0; s < 16; s++)
		{
			int b = 0, r = n, c = m;
			if(s&1)
			{
				r--;
				b++;
			}
			if(s&2)
			{
				r--;
				b++;
			}
			if(s&4)
			{
				c--;
				b++;
			}
			if(s&8)
			{
				c--;
				b++;
			}
			if(b&1)
				sum = ((sum - C[r*c][k]) % mod + mod) % mod;
			else
				sum = (sum + C[r*c][k]) % mod;
		}
		printf("Case %d: %d
", cas++, sum);
	}
	return 0;
}