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 <vector>
#include <algorithm>
#include <utility>
using namespace std;

#define P 10007
#define modp(x) ((((x)%P)+P)%P)

int fac[40];

int calc2(int n,int a,int b,int c,int d){
	vector<int> hoge(n+1);
	hoge[0]=1;
	for(int t=0;t<a;t++){
		for(int i=n;i>=0;i--){
			if(i>=1)hoge[i]=modp(hoge[i]+4*hoge[i-1]);
			if(i>=2)hoge[i]=modp(hoge[i]+2*hoge[i-2]);
		}
	}
	for(int t=0;t<b;t++){
		for(int i=n;i>=0;i--){
			if(i>=1)hoge[i]=modp(hoge[i]+2*hoge[i-1]);
		}
	}
	for(int t=0;t<c;t++){
		for(int i=n;i>=0;i--){
			if(i>=1)hoge[i]=modp(hoge[i]+2*hoge[i-1]);
		}
	}
	for(int t=0;t<d;t++){
		for(int i=n;i>=0;i--){
			if(i>=1)hoge[i]=modp(hoge[i]+hoge[i-1]);
		}
	}
	int ret=0;
	for(int i=0;i<=n;i++){
		ret=modp(ret+fac[n-i]*hoge[i]*(i%2==0?1:-1));
	}
	return ret;
}

int calc(int n,vector<pair<int,int> > ng){
	int k=ng.size();
	int ret=0;
	for(int b=0;b<(1<<k);b++){
		bool collide=false;
		for(int i=0;i<k;i++)for(int j=0;j<k;j++)if(i!=j && (b&(1<<i))!=0 && (b&(1<<j))!=0 && (ng[i].first==ng[j].first || ng[i].second==ng[j].second))collide=true;
		if(collide)continue;
		for(int d=0;d<4;d++){
			int sn=((__builtin_popcount(b)+__builtin_popcount(d))%2==0)?1:-1;
			bool ok=true;
			if(d&1){
				for(int i=0;i<k;i++)if((b&(1<<i))!=0 && ng[i].first==ng[i].second)ok=false;
			}
			if(d&2){
				for(int i=0;i<k;i++)if((b&(1<<i))!=0 && ng[i].first==n-1-ng[i].second)ok=false;
			}
			if(ok){
				vector<int> row(n),col(n);
				for(int i=0;i<k;i++)if((b&(1<<i))!=0)row[ng[i].first]=col[ng[i].second]=1;
				//calculate parameters
				int m=n-__builtin_popcount(b),p=0,q=0,r=0,s=0;
				if(d==1){
					for(int i=0;i<n;i++)if(row[i]==0&&col[i]==0)s++;
				}
				if(d==2){
					for(int i=0;i<n;i++)if(row[i]==0&&col[n-1-i]==0)s++;
				}
				if(d==3){
					for(int i=0;i<n-1-i;i++){
						if(row[i]+row[n-1-i]==0 && col[i]+col[n-1-i]==0)p++;
						if(row[i]+row[n-1-i]==0 && col[i]+col[n-1-i]==1)q++;
						if(row[i]+row[n-1-i]==1 && col[i]+col[n-1-i]==0)r++;
						if(row[i]+row[n-1-i]==1 && col[i]+col[n-1-i]==1)s++;
						
					}
					if((n-1)%2==0 && row[(n-1)/2]==0 && col[(n-1)/2]==0)s++;
				}
				ret=modp(ret+sn*calc2(m,p,q,r,s));
			}
		}
	}
	return ret;
}

int main(){
	fac[0]=1;for(int i=1;i<40;i++)fac[i]=modp(fac[i-1]*i);
	int n,k;
	scanf("%d%d",&n,&k);
	vector<pair<int,int> > ng(k);
	for(int i=0;i<k;i++)scanf("%d%d",&ng[i].first,&ng[i].second);
	printf("%d\n",calc(n,ng));
}