Description：

给一个 $n\times n$ 的棋盘，放 $n$ 个棋子使得每行每列还有两个主对角线都有棋子，并且给定的 $m$ 个位置没有棋子。

$1\leqslant n\leqslant 100,1\leqslant m\leqslant 10$

Solution：

首先显然可以对 $m$ 容斥，然后问题就变成了统计在一些位置一定填了棋子的情况下的方案数，那么我们可以再容斥变成 $(n-tot)!-$ 某一个对角线上为空或者两个对角线上都为空，这个取决于必须填的位置是否在对角线上，这个的求法我们还可以再容斥，如果只是要求某一个对角线为空，那么容斥为： $$ \sum_{i=0}^{blk}(-1)^i\binom{blk}{i}(tot-i)! $$ 如果容斥时要求两个对角线都为空，那么把棋盘分成一圈一圈的，显然圈之间互不影响，于是可以做一遍背包统计出选 $k$ 个的方案数，然后把上面那个式子的组合数替换成这个方案数容斥，于是这道题就是一个容斥套容斥套容斥。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXM 11

int cnt[1 << MAXM];

int x[MAXM],y[MAXM];

#define MOD 10007

int bit(int s,int p){return ((s >> (p - 1)) & 1);}

#define MAXN 110

bool visx[MAXN],visy[MAXN];

int fac[MAXN],inv[MAXN];

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;

}

int C(int n,int m)

{

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

}

int calcempty(int blk,int tot)

{

	int res = 0;

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

	{

		res = (res + 1ll * ((i & 1) ? MOD - 1 : 1) * C(blk,i) % MOD * fac[tot - i] % MOD) % MOD;

	}

	return res;

}

int f[MAXN];

int calc(int s)

{

	memset(visx,false,sizeof(visx));

	memset(visy,false,sizeof(visy));

	bool tag1 = false,tag2 = false;

	int tot = 0;

	for(int i = 1;i <= m;++i)

	{

		if(bit(s,i) && (visx[x[i]] || visy[y[i]]))return 0;

		if(bit(s,i))visx[x[i]] = visy[y[i]] = true;

		if(bit(s,i) && x[i] == y[i])tag1 = true;

		if(bit(s,i) && x[i] + y[i] == n + 1)tag2 = true;

		if(bit(s,i))++tot;

	}

	if(tag1 && tag2)return fac[n - tot];

	int blk1 = 0,blk2 = 0;

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

	{

		if(!visx[i] && !visy[i])++blk1;

		if(!visx[i] && !visy[n + 1 - i])++blk2;

	}//cout << blk1 << " " << blk2 << endl; 

	if(tag1)return (fac[n - tot] - calcempty(blk2,n - tot) + MOD) % MOD;

	if(tag2)return (fac[n - tot] - calcempty(blk1,n - tot) + MOD) % MOD;

	int empcnt3 = 0;

	memset(f,0,sizeof(f));

	f[0] = 1;

	int mx = n - tot;

	for(int i = 1;i <= (n + 1) / 2;++i)

	{

		if((n & 1) && i == (n + 1) / 2 && !visx[i] && !visy[i])

		{

			for(int j = mx;j >= 1;--j)f[j] = (f[j] + f[j - 1]) % MOD;

		}

		else

		{

			if(visx[i] && visx[n - i + 1])continue;

			if(visy[i] && visy[n - i + 1])continue;

			if((visx[i] ^ visx[n - i + 1]) && (visy[i] ^ visy[n - i + 1]))

			{

				for(int j = mx;j >= 1;--j)f[j] = (f[j] + f[j - 1]) % MOD;

				continue;

			}

			if((visx[i] ^ visx[n - i + 1]) || (visy[i] ^ visy[n - i + 1]))

			{

				for(int j = mx;j >= 1;--j)f[j] = (f[j] + f[j - 1] * 2 % MOD) % MOD;

				continue;

			}

			for(int j = mx;j >= 1;--j)f[j] = ((f[j] + 4ll * f[j - 1] % MOD) % MOD + (j >= 2 ? f[j - 2] : 0) * 2 % MOD) % MOD;

		}

	}

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

	{//cout << i << " ->  " << f[i] << endl;

		empcnt3 = (empcnt3 + 1ll * ((i & 1) ? MOD - 1 : 1) * f[i] % MOD * fac[n - tot - i] % MOD) % MOD;

	}//cout << s << " : " << fac[mx] << " " << calcempty(blk1,mx) << " " << calcempty(blk2,mx) << " " << empcnt3 << " " << fac[mx] - calcempty(blk1,mx) - calcempty(blk2,mx) + empcnt3 << endl;

	int res = (((fac[mx] - calcempty(blk1,mx) + MOD) % MOD - calcempty(blk2,mx) + MOD) % MOD + empcnt3) % MOD;

	return res;

}

void work()

{

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

	for(int i = 1;i <= m;++i)scanf("%d%d",&x[i],&y[i]);

	for(int i = 1;i <= m;++i)++x[i],++y[i];

	fac[0] = 1;

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

	inv[n] = power(fac[n],MOD - 2);

	for(int i = n - 1;i >= 0;--i)inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;

	memset(cnt,0,sizeof(cnt));

	for(int s = 0;s < (1 << m);++s)

	{

		for(int i = 1;i <= m;++i)if(bit(s,i))++cnt[s];

		if(cnt[s] & 1)cnt[s] = MOD - 1;

		else cnt[s] = 1;

	}

	int ans = 0;

	for(int s = 0;s < (1 << m);++s)

	{

		int res = calc(s);//if(res != 0)cout << s << " " << res << endl;

		ans = (ans + 1ll * cnt[s] * res % MOD) % MOD;

	}

	cout << ans << endl;

	return;

}

int main()

{

	int testcases;

	scanf("%d",&testcases);

	while(testcases--)work();

	return 0;

}