https://code.google.com/codejam/contest/32002/dashboard#s=p3

endless_knight.cpp

#include <bits/stdc++.h>

using namespace std;

const int MOD = 10007;

int fact[MOD], inv[MOD];

int r[10], c[10];

template<typename... Ts>
inline int mult(Ts...)
{
	return 1;
}

template<typename T, typename... Ts>
inline int mult(T a, Ts... b)
{
	return a * mult(b...) % MOD;
}

int povrh(int a, int b)
{
	if (a < 0 || b < 0 || a - b < 0)
		return 0;
	
	if (a < MOD && b < MOD)
		return mult(fact[a], inv[b], inv[a - b]);
	
	int res = 1;
	while (a || b)
	{
		res *= povrh(a % MOD, b % MOD);
		res %= MOD;
		a /= MOD;
		b /= MOD;
	}
	
	return res;
}

inline int nacina(int a, int b)
{
	return (a + b) % 3 ? 0 : povrh((a + b) / 3, (2 * a - b) / 3);
}

void init()
{
	fact[0] = inv[0] = 1;
	for (int i = 1; i < MOD; ++i)
	{
		fact[i] = i * fact[i - 1] % MOD;
		
		for (inv[i] = 1; inv[i] * fact[i] % MOD != 1; ++inv[i]);
	}
}

void work(int t)
{
	static vector<pair<int, int>> v;
	int h, w, k, i;
	int sol = 0, num;
	
	cin>>h>>w>>k;
	
	for (i = 0; i < k; ++i)
		cin>>r[i]>>c[i];
	
	for (int bit = 0; bit < (1<<k); ++bit)
	{
		v.clear();
		v.emplace_back(1, 1);
		for (i = 0; i < k; ++i) if (bit & (1<<i))
			v.emplace_back(r[i], c[i]);
		v.emplace_back(h, w);
		sort(v.begin(), v.end());
		
		num = 1;
		for (i = 1; i < v.size(); ++i)
			num *= nacina(v[i].first - v[i - 1].first, v[i].second - v[i - 1].second), num %= MOD;
		
		if (__builtin_parity(bit))
			num = MOD - num;
		
		sol += num;
		sol %= MOD;
	}
	
	cout<<"Case #"<<t<<": "<<sol<<endl;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	init();
	
	int n;
	
	cin>>n;
	
	for (int i = 1; i <= n; ++i)
		work(i);
}