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>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 99999999999999999
//#define MOD 1000000007
#define EPS 0.000000001
using namespace std;



#define MOD 10007


enum Type{
	N,
	E,
	S,
	W,
	NE,
	SE,
	NW,
	SW,
};

struct Info{

	int x,y;
};


int SIZE,K;
int POW[9],dp[18][33][4];
bool check_X[32],check_Y[32];
vector<int> STATE;
vector<Info> V;
Info info[8];

void mod_add(int &A,int B){

	A += B;
	A %= MOD;
}


int func(){

	for(int i = 0; i <= SIZE/2+1; i++){
		for(int k = 0; k <= SIZE; k++){
			for(int a = 0; a < POW[2]; a++){

				dp[i][k][a] = 0;
			}
		}
	}

	for(int i = 0; i < SIZE; i++){
		check_X[i] = false;
		check_Y[i] = false;
	}

	int first_cross = 0;

	for(int i = 0; i < V.size(); i++){

		if(check_X[V[i].x] || check_Y[V[i].y]){

			return 0;
		}
		check_X[V[i].x] = true;
		check_Y[V[i].y] = true;

		if(V[i].x == V[i].y){ //右上がり

			first_cross |= POW[0];
		}
		if(V[i].x+V[i].y == SIZE-1){ //右下がり

			first_cross |= POW[1];
		}
	}

	int first = 0;
	dp[first][0][first_cross] = 1;
	int last;
	if(SIZE%2 == 0){

		last = SIZE/2-1;
	}else{

		last = SIZE/2;
	}

	int LU = (SIZE-1)/2;
	int RD = SIZE/2;


	int num_X,num_Y;
	int work[8];
	int next_state,mult_X,mult_Y,add,tmp;

	int num_fix = V.size();

	for(int range = first; range <= last; range++){

		num_X = 0;
		num_Y = 0;

		for(int k = LU+1; k <= RD-1; k++){
			if(!check_X[k]){
				num_X++;
			}
			if(!check_Y[k]){

				num_Y++;
			}
		}

		for(int i = 0; i <= SIZE-num_fix; i++){
			for(int state = 0; state < POW[2]; state++){
				if(dp[range][i][state] == 0)continue;

				if(range == first && SIZE%2 == 1){

					mod_add(dp[range+1][i][state],dp[range][i][state]);
					if(!check_X[LU] && !check_Y[LU] && i+1 <= SIZE-num_fix){

						mod_add(dp[range+1][i+1][POW[2]-1],dp[range][i][state]);
					}

				}else{

					for(int k = 0; k < STATE.size(); k++){

						add = 0;

						int ST = STATE[k];
						for(int loop = 0; loop < 8; loop++){
							if(ST & (POW[loop])){

								work[loop] = 1;
								add++;

							}else{

								work[loop] = 0;
							}
						}

						if(i+add > SIZE-num_fix)continue;

						if(range == first && SIZE%2 == 0){
							if(work[N]+work[E]+work[S]+work[W] != 0){

								continue;
							}
						}

						if((check_Y[LU] && (work[SW]+work[S]+work[SE] != 0)) ||
								(check_Y[RD] && (work[NW]+work[N]+work[NE] != 0))){

							continue;
						}
						if((check_X[LU] && (work[NW]+work[W]+work[SW] != 0)) ||
								(check_X[RD] && (work[NE]+work[E]+work[SE] != 0))){

							continue;
						}

						next_state = state;
						if(work[SW] == 1 || work[NE] == 1){

							next_state |= POW[0];
						}
						if(work[NW] == 1 || work[SE] == 1){

							next_state |= POW[1];
						}

						switch(work[N]+work[S]){
						case 2:
							mult_X = (num_X-i)*(num_X-i-1);
							break;
						case 1:
							mult_X = (num_X-i);
							break;
						case 0:
							mult_X = 1;
							break;
						}

						switch(work[E]+work[W]){
						case 2:
							mult_Y = (num_Y-i)*(num_Y-i-1);
							break;
						case 1:
							mult_Y = (num_Y-i);
							break;
						case 0:
							mult_Y = 1;
							break;
						}

						tmp = mult_X*mult_Y;
						tmp *= dp[range][i][state];
						tmp %= MOD;

						mod_add(dp[range+1][i+add][next_state],tmp);
					}
				}
			}
		}

		LU--;
		RD++;
	}

	return dp[last+1][SIZE-num_fix][POW[2]-1];
}

void calc_state(){

	int check[8];

	for(int state = 0; state < POW[8]; state++){
		for(int loop = 0; loop < 8; loop++){
			if(state & (POW[loop])){

				check[loop] = 1;

			}else{

				check[loop] = 0;
			}
		}

		if((check[NW]+check[N]+check[NE] > 1)||(check[NE]+check[E]+check[SE] > 1)||
				(check[SE]+check[S]+check[SW] > 1)||(check[SW]+check[W]+check[NW] > 1)){
			continue;
		}
		STATE.push_back(state);
	}
}


int main(){

	POW[0] = 1;
	for(int i = 1; i <= 8; i++){

		POW[i] = POW[i-1]*2;
	}

	calc_state();

	scanf("%d %d",&SIZE,&K);

	for(int i = 0; i < K; i++){

		scanf("%d %d",&info[i].x,&info[i].y);
	}

	int ans = 0;
	int count,tmp;

	for(int state = 0; state < POW[K]; state++){

		V.clear();
		count = 0;

		for(int loop = 0; loop < K; loop++){
			if(state & POW[loop]){
				V.push_back(info[loop]);
				count++;
			}
		}

		tmp = func();

		if(count%2 == 0){

			ans += tmp;
			ans %= MOD;

		}else{

			ans = (ans-tmp+MOD)%MOD;
		}
	}

	printf("%d\n",ans);

	return 0;
}