Problem: Bingo is a party game played by many players and one game master. Each player is given a bingo card containing N2 different numbers in a N × N grid (typically N = 5). The master draws numbers from a lottery one by one during the game. Each time a number is drawn, a player marks a square with that number if it exists. The player’s goal is to have N marked squares in a single vertical, horizontal, or diagonal line and then call “Bingo!” The first player calling “Bingo!” wins the game.

In ultimately unfortunate cases, a card can have exactly N unmarked squares, or N(N-1) marked squares, but not a bingo pattern. Your task in this problem is to write a program counting how many such patterns are possible from a given initial pattern, which contains zero or more marked squares.



Input

The input is given in the following format:

N K
x1 y1
.
.
.
xK yK


The input begins with a line containing two numbers N (1 ≤ N ≤ 32) and K (0 ≤ K ≤ 8), which represent the size of the bingo card and the number of marked squares in the initial pattern respectively. Then K lines follow, each containing two numbers xi and yi to indicate the square at (xi, yi) is marked. The coordinate values are zero-based (i.e. 0 ≤ xi, yi ≤ N - 1). No pair of marked squares coincides.

Output

Count the number of possible non-bingo patterns with exactly N unmarked squares that can be made from the given initial pattern, and print the number in modulo 10007 in a line (since it is supposed to be huge). Rotated and mirrored patterns should be regarded as different and counted each.

Examples

Input

4 2
0 2
3 1


Output

6


Input

4 2
2 3
3 2


Output

6


Input

10 3
0 0
4 4
1 4


Output

1127

Solution (in CPP):

Solution:
#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
int mod=10007;
int r[10];
int c[10];
int n;
int dp[40][40][4];
int dp2[40][40][4][4][5][3];
int v[40][40];
int calc(vector<pair<int,int> > p){
	for(int i=0;i<40;i++)for(int j=0;j<40;j++)for(int k=0;k<4;k++)
		dp[i][j][k]=0;
	for(int i=0;i<p.size();i++)for(int j=i+1;j<p.size();j++){
		if(p[i].first==p[j].first||p[i].second==p[j].second)return 0;
	}
	for(int i=0;i<40;i++)for(int j=0;j<40;j++)v[i][j]=0;
	for(int i=0;i<p.size();i++){
		v[p[i].first][p[i].second]=1;
	}
	dp[0][0][0]=1;
	bool ok=true;
	for(int i=0;i<p.size();i++)if(n/2==p[i].first||n/2==p[i].second)ok=false;
	if(n%2&&ok)dp[0][1][3]=1;
	for(int i=0;i<n/2;i++){
		int hu=0;
		int wu=0;
		int he=0;
		int we=0;
		for(int j=0;j<p.size();j++){
			if(p[j].first==n/2-1-i)he|=1;
			if(p[j].first==(n+1)/2+i)he|=2;
			if(p[j].second==n/2-1-i)we|=1;
			if(p[j].second==(n+1)/2+i)we|=2;
			if(n/2-1-i<p[j].first&&p[j].first<(n+1)/2+i)hu++;
			if(n/2-1-i<p[j].second&&p[j].second<(n+1)/2+i)wu++;
		}
	//	printf("%d: %d %d %d %d\n",i,hu,wu,he,we);
		for(int j=0;j<40;j++){
			for(int k=0;k<4;k++){
				if(!dp[i][j][k])continue;
		//		if(i*2+n%2-j-hu<0||i*2+n%2-j-wu<0)printf("%d %d %d: %d %d %d\n",i,j,k,dp[i][j][k],hu,wu);
				if(i*2+n%2-j-hu<0||i*2+n%2-j-wu<0)continue;
				for(int l=0;l<=4;l++){
					dp[i+1][j+l][k]=(dp[i+1][j+l][k]+dp[i][j][k]*dp2[i*2+n%2-j-hu][i*2+n%2-j-wu][he][we][l][0])%mod;
					dp[i+1][j+l][k|1]=(dp[i+1][j+l][k|1]+dp[i][j][k]*dp2[i*2+n%2-j-hu][i*2+n%2-j-wu][he][we][l][1])%mod;
					dp[i+1][j+l][k|2]=(dp[i+1][j+l][k|2]+dp[i][j][k]*dp2[i*2+n%2-j-hu][i*2+n%2-j-wu][he][we][l][2])%mod;
				}
			}
		}
	}
	int ret=dp[n/2][n-(int)p.size()][3];
	bool t1=false;
	bool t2=false;
	for(int i=0;i<p.size();i++){
		if(p[i].first==p[i].second)t1=true;
		if(p[i].first+p[i].second==n-1)t2=true;
	}
	if(t1)ret=(ret+dp[n/2][n-(int)p.size()][2])%mod;
	if(t2)ret=(ret+dp[n/2][n-(int)p.size()][1])%mod;
	if(t1&&t2)ret=(ret+dp[n/2][n-(int)p.size()][0])%mod;
	return ret;
}
int main(){
	int a,b;
	scanf("%d%d",&a,&b);
	n=a;
	for(int i=0;i<b;i++)scanf("%d%d",r+i,c+i);
	int ret=0;
	for(int i=0;i<40;i++)for(int j=0;j<40;j++){
		for(int k=0;k<4;k++)for(int l=0;l<4;l++){
			dp2[i][j][k][l][0][0]=1;
			int s1=2-__builtin_popcount(k);
			int s2=2-__builtin_popcount(l);
			dp2[i][j][k][l][1][0]=i*s2+j*s1;
			dp2[i][j][k][l][2][0]=(i*(i-1)*(s2/2)+j*(j-1)*(s1/2)+i*j*s1*s2)%mod;
			if(s1==1&&s2==2){
				dp2[i][j][k][l][3][0]=j*i*(i-1)%mod;
			}
			if(s1==2&&s2==1){
				dp2[i][j][k][l][3][0]=i*j*(j-1)%mod;
			}
			if(s1==2&&s2==2){
				dp2[i][j][k][l][3][0]=(j*i*(i-1)+i*j*(j-1))*2%mod;
				dp2[i][j][k][l][4][0]=i*(i-1)*j*(j-1)%mod;
			}
			int t1=0;
			int t2=0;
			if(!(k&1)&&!(l&1))t1++;
			if(!(k&2)&&!(l&2))t1++;
			if(!(k&1)&&!(l&2))t2++;
			if(!(k&2)&&!(l&1))t2++;
			dp2[i][j][k][l][1][1]=t1;
			dp2[i][j][k][l][1][2]=t2;
			if(t1==2){
				dp2[i][j][k][l][2][1]=2*(i+j)+1;
				dp2[i][j][k][l][3][1]=2*i*j;
			}else if(t1==1&&k==0)dp2[i][j][k][l][2][1]=j;
			else if(t1==1&&l==0)dp2[i][j][k][l][2][1]=i;
			if(t2==2){
				dp2[i][j][k][l][2][2]=2*(i+j)+1;
				dp2[i][j][k][l][3][2]=2*i*j;
			}else if(t2==1&&k==0)dp2[i][j][k][l][2][2]=j;
			else if(t2==1&&l==0)dp2[i][j][k][l][2][2]=i;
		}
	}
//	for(int i=0;i<5;i++)for(int j=0;j<5;j++){
//		for(int k=0;k<=4;k++)printf("%d %d %d: %d\n",i,j,k,dp2[i][j][1][0][k][0]);
//	}
	for(int i=0;i<(1<<b);i++){
		int t=__builtin_popcount(i);
		vector<pair<int,int> > p;
		for(int j=0;j<b;j++)if(i&(1<<j))p.push_back(make_pair(r[j],c[j]));
		int val=calc(p);
	//	printf("%d: %d\n",i,val);
		if(t%2)ret=(ret+mod-val)%mod;
		else ret=(ret+val)%mod;
	}
	printf("%d\n",ret);
}