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 <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define rep1(i,n) for(int i=1;i<=(int)(n);i++)
#define all(c) c.begin(),c.end()
#define pb push_back
#define fs first
#define sc second
#define show(x) cout << #x << " = " << x << endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
using namespace std;
int N,mod=10007;
vector<int> _bs;
inline int P(int x,int y){
	if(y==0) return 1;
	if(y==1) return x;
	if(y==2) return x*(x-1);
}
inline void add(int &x,int y){
	x+=y;
	x%=mod;
}
int solve(vector<int> x,vector<int> y){
	int K=x.size();
	int dp[17][33][2][2]={};		//	,put,sl,bsl
	bool banx[32]={},bany[32]={};
	bool sl=0,bsl=0;
	rep(i,K){
		if(banx[x[i]]||bany[y[i]]) return 0;
		banx[x[i]]=bany[y[i]]=1;
		if(x[i]==y[i]) bsl=1;
		if(x[i]+y[i]==N-1) sl=1;
	}
	dp[0][0][sl][bsl]=1;
	int L=-N%2,M=(N+1)/2;
	int A=(N-1)/2,B=N/2;
	rep(i,M){//it
		int X=0,Y=0;
		for(int j=A+1;j<=B-1;j++){
			if(!banx[j]) X++;
			if(!bany[j]) Y++;
		}
		rep(j,N+1-K){//put
			rep(k,2) rep(l,2){//sl,bsl
				if(dp[i][j][k][l]==0) continue;
				if(L==-1){
					add(dp[i+1][j][k][l],dp[i][j][k][l]);
					if(!banx[A]&&!bany[A]&&j+1<=N-K) add(dp[i+1][j+1][1][1],dp[i][j][k][l]);
				}else{
					for(int b:_bs){
						bool bs[8]={};
						int C=0;
						rep(a,8) bs[a]=(b>>a)&1;
						rep(a,8) if(bs[a]) C++;
						if(L==0&&(bs[4]||bs[5]||bs[6]||bs[7])) continue;
						if(banx[A]&&(bs[0]||bs[4]||bs[1])) continue;
						if(banx[B]&&(bs[2]||bs[6]||bs[3])) continue;
						if(bany[A]&&(bs[3]||bs[7]||bs[0])) continue;
						if(bany[B]&&(bs[1]||bs[5]||bs[2])) continue;
						int ad=P(Y-j,bs[4]+bs[6])*P(X-j,bs[5]+bs[7])%mod*dp[i][j][k][l];
						if(ad) add(dp[i+1][j+C][k|bs[1]||bs[3]][l|bs[0]|bs[2]],ad);
					}
				}
			}
		}
		A--,B++,L+=2;
	}
/*	rep(i,M+1) rep(j,N+1-K) rep(k,2) rep(l,2){
		printf("dp[%d][%d][%d][%d]=%d\n",i,j,k,l,dp[i][j][k][l]);
	}
	puts("");*/
	return dp[M][N-K][1][1];
}
int xx[8],yy[8];
int main(){
	rep(i,1<<8){
		bool b[8]={};
		rep(j,8) b[j]=(i>>j)&1;
		bool ok=1;
		if(b[0]+b[4]+b[1]>1) ok=0;
		if(b[1]+b[5]+b[2]>1) ok=0;
		if(b[2]+b[6]+b[3]>1) ok=0;
		if(b[3]+b[7]+b[0]>1) ok=0;
		if(ok) _bs.pb(i);
	}
	int K;
	cin>>N>>K;
	rep(i,K) cin>>xx[i]>>yy[i];
	int ans=0;
	rep(i,1<<K){
		vector<int> x,y;
		rep(j,K) if((i>>j)&1) x.pb(xx[j]),y.pb(yy[j]);
		int t=1;
		if(x.size()%2) t=-1;
		int tmp=solve(x,y)*t;
//		show(i);
//		show(tmp);
		add(ans,tmp);
	}
	cout<<(ans+mod)%mod<<endl;
}