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>
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
typedef pair<int,P> P1;
typedef pair<P,P> P2;
#define pu push
#define pb push_back
#define mp make_pair
#define eps 1e-7
#define INF 1000000000
#define mod 10007
#define fi first
#define sc second
#define rep(i,x) for(int i=0;i<x;i++)
#define repn(i,x) for(int i=1;i<=x;i++)
#define SORT(x) sort(x.begin(),x.end())
#define ERASE(x) x.erase(unique(x.begin(),x.end()),x.end())
#define POSL(x,v) (lower_bound(x.begin(),x.end(),v)-x.begin())
#define POSU(x,v) (upper_bound(x.begin(),x.end(),v)-x.begin())
int n,k;
int a[10],b[10];
int x[35];
bool used[35];
ll dp[55][55][2],f;
int main(){
	cin >> n >> k;
	for(int i=0;i<k;i++) cin >> a[i] >> b[i];
	ll ans = 0;
	for(int mask=0;mask<(1<<k);mask++){
		for(int i=0;i<n;i++) x[i] = -1, used[i] = 0;
		bool bad = 0;
		for(int i=0;i<k;i++){
			if(((mask>>i)&1)){
				if(x[a[i]] != -1 && x[a[i]] != b[i]) bad = 1;
				if(used[b[i]]) bad = 1;
				x[a[i]] = b[i];
				used[b[i]] = 1;
			}
		}
		if(bad) continue;
		ll val = 0;
		//not consider both lines
		int C = 0;
		for(int i=0;i<n;i++) if(x[i] == -1) C++;
		ll mm = 1;
		for(int i=1;i<=C;i++) mm = mm*1LL*i%mod;
		val = (val+mm)%mod;
		//consider only one line (x = y)
		memset(dp,0LL,sizeof(dp));
		dp[0][0][0] = 1;
		for(int i=0;i<n;i++){
			for(int j=0;j<=i;j++){
				if(x[i] == i || (!used[i] && x[i] == -1)){
					rep(q,2) dp[i+1][j][1-q] = (dp[i+1][j][1-q]+dp[i][j][q])%mod;
				}
			    {
					int add = (x[i] == -1);
					rep(q,2) dp[i+1][j+add][q] = (dp[i+1][j+add][q]+dp[i][j][q])%mod;
				}
			}
		}
		f = 1;
		for(int i=0;i<=n;i++){
			val -= dp[n][i][0] * f % mod;
			val += dp[n][i][1] * f % mod;
			f = f*1LL*(i+1)%mod;
		}
		//consider only one line (x+y = n-1)
		memset(dp,0LL,sizeof(dp));
		dp[0][0][0] = 1;
		for(int i=0;i<n;i++){
			for(int j=0;j<=i;j++){
				if(x[i] == n-1-i || (!used[n-1-i] && x[i] == -1)){
					rep(q,2) dp[i+1][j][1-q] = (dp[i+1][j][1-q]+dp[i][j][q])%mod;
				}
				{
					int add = (x[i] == -1);
					rep(q,2) dp[i+1][j+add][q] = (dp[i+1][j+add][q]+dp[i][j][q])%mod;
				}
			}
		}
		f = 1;
		for(int i=0;i<=n;i++){
			val -= dp[n][i][0] * f % mod;
			val += dp[n][i][1] * f % mod;
			f = f*1LL*(i+1)%mod;
		}
		//consider both lines (x = y & x+y = n-1)
		memset(dp,0LL,sizeof(dp));
		dp[0][0][0] = 1;
		int last = 0;
		for(int i=0;i<=n-1-i;i++){
		    last = i+1;
			for(int j=0;j<=2*i;j++){
				//i & n-1-i
				//both
				if(i != n-1-i){
					if(x[i] != -1 && x[i] != i && x[i] != n-1-i) goto nxt;
					if(x[n-1-i] != -1 && x[n-1-i] != i && x[n-1-i] != n-1-i) goto nxt;
					bool fail = 0;
					for(int k=0;k<n;k++) if(k != i && k != n-1-i && (x[k] == i || x[k] == n-1-i)) fail = 1;
					if(fail) goto nxt;
					int mul = 2;
					if(x[i] != -1 || x[n-1-i] != -1) mul = 1;
					rep(q,2) dp[i+1][j][q] = (dp[i+1][j][q]+dp[i][j][q]*1LL*mul)%mod;
				}
				nxt:;
				if(i != n-1-i){
					if(x[i] != -1 && x[i] != i && x[i] != n-1-i) goto nxt2;
					int fail = 0;
					for(int k=0;k<n;k++) if(k != i && (x[k] == i || x[k] == n-1-i)) fail += 1;
					if(fail == 2) goto nxt2;
					int add = (x[n-1-i] == -1);
					int mul = 2-fail;
					if(x[i] != -1) mul = 1;
					rep(q,2) dp[i+1][j+add][1-q] = (dp[i+1][j+add][1-q]+dp[i][j][q]*1LL*mul)%mod;
				}
				else{
				    if(x[i] != -1 && x[i] != i) goto nxt2;
					int fail = 0;
					for(int k=0;k<n;k++) if(k != i && (x[k] == i)) fail += 1;
					if(fail == 1) goto nxt2;
					int add = 0;
					int mul = 1;
					rep(q,2) dp[i+1][j+add][1-q] = (dp[i+1][j+add][1-q]+dp[i][j][q]*1LL*mul)%mod;
				}
				nxt2:;
				if(i != n-1-i){
					if(x[n-1-i] != -1 && x[n-1-i] != i && x[n-1-i] != n-1-i) goto nxt3;
					int fail = 0;
					for(int k=0;k<n;k++) if(k != n-1-i && (x[k] == i || x[k] == n-1-i)) fail += 1;
					if(fail == 2) goto nxt3;
					int add = (x[i] == -1);
					int mul = 2-fail;
					if(x[n-1-i] != -1) mul = 1;
					rep(q,2) dp[i+1][j+add][1-q] = (dp[i+1][j+add][1-q]+dp[i][j][q]*1LL*mul)%mod;
				}
				nxt3:;
				if(i != n-1-i){
					int add = (x[i] == -1) + (x[n-1-i] == -1);
					rep(q,2) dp[i+1][j+add][q] = (dp[i+1][j+add][q]+dp[i][j][q])%mod;
				}
				else{
				    int add = (x[i] == -1) ;
					rep(q,2) dp[i+1][j+add][q] = (dp[i+1][j+add][q]+dp[i][j][q])%mod;
				}
			}
		}
		f = 1;
		for(int i=0;i<=n;i++){
			val += dp[last][i][0] * f % mod;
			val -= dp[last][i][1] * f % mod;
			f = f*1LL*(i+1)%mod;
		}
		if(__builtin_popcount(mask)%2 == 0) ans = (ans+val)%mod;
		else ans = (ans-val)%mod;
	}
	cout << (ans+mod)%mod << endl;
}