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;

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#define REACH cerr<<"reached line "<<__LINE__<<endl
#define DBG(x) cerr<<"line "<<__LINE__<<" "<<#x<<":"<<x<<endl

using uint=unsigned int;
using ll=long long;
using pii=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"[";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"]";
	return os;
}

int read(){
	int i;
	scanf("%d",&i);
	return i;
}

ll readLL(){
	ll i;
	scanf("%lld",&i);
	return i;
}

string readString(){
	static char buf[3341919];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341919];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(a>b)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

const int mod=10007;
template<class T,class U>
void add(T& a,U b){
	a=((ll)a+b)%mod;
}

template<class T,class U>
void sub(T& a,U b){
	a=((ll)a-b%mod+mod)%mod;
}

template<class T,class U>
void mult(T& a,U b){
	a=((ll)a*b)%mod;
}

ll modPow(ll a,ll p){
	ll s=1;
	REP(i,30){
		if((p>>i)&1)
			mult(s,a);
		mult(a,a);
	}
	return s;
}

ll modInv(ll a){
	return modPow(a,mod-2);
}

struct Wafrelka{
	int n,m;
	vector<vi> graph;
	Wafrelka(int _n,int _m):n(_n),m(_m){
		graph.assign(n,vi());
	}
	void AddEdge(int a,int b){
		graph[a].PB(b);
	}
	vi CountMatching(){
		int maxMatch=min(n,m);
		vector<vi> dp(maxMatch+1,vi(1<<m,0));
		dp[0][0]=1;
		REP(i,n)
			for(int j=maxMatch-1;j>=0;j--)
				REP(vis,1<<m)
					for(auto to:graph[i])if(!((vis>>to)&1))
						add(dp[j+1][vis|(1<<to)],dp[j][vis]);
		vi ret(maxMatch+1,0);
		REP(i,maxMatch+1)
			REP(j,1<<m)
				add(ret[i],dp[i][j]);
		return ret;
	}
};

struct Solver{
	int n;
	vector<vi> graph;
	Solver(int _n):n(_n){
		graph.assign(n*2,vi());
	}
	void AddEdge(int a,int b){
		graph[a].PB(b+n);
		graph[b+n].PB(a);
	}
	void dfs(int v,vector<bool>& vis,vi& left,vi& right){
		if(vis[v])
			return;
		if(v<n)
			left.PB(v);
		else
			right.PB(v);
		vis[v]=true;
		for(auto to:graph[v])
			dfs(to,vis,left,right);
	}
	int CountPerfectMatching(){
		vector<bool> vis(n*2,false);
		vi cur(n+1,0),nx(n+1,0);
		cur[0]=1;
		REP(i,n)if(!vis[i]){
			vi left,right;
			dfs(i,vis,left,right);
			Wafrelka w(left.size(),right.size());
			REP(j,left.size())
				for(auto to:graph[left[j]])
					REP(k,right.size())if(to==right[k])
						w.AddEdge(j,k);
			vi t=w.CountMatching();
			fill(ALL(nx),0);
			REP(j,n+1)REP(k,t.size())if(j+k<n+1)
				add(nx[j+k],cur[j]*t[k]);
			swap(cur,nx);
		}
		int c=1,ret=0;
		for(int i=n;i>=0;i--){
			if(i&1)
				sub(ret,cur[i]*c);
			else
				add(ret,cur[i]*c);
			c=c*(n-i+1)%mod;
		}
		return ret;
	}
};

int main(){
	int n=read(),k=read();
	vector<pii> es;
	REP(i,k){
		int x=read(),y=read();
		es.PB(MP(x,y));
	}
	int ans=0;
	{
		vector<vector<bool>> c(n,vector<bool>(n,false));
		for(auto e:es)
			c[e.first][e.second]=true;
		Solver sv(n);
		REP(i,n)REP(j,n)if(c[i][j])
			sv.AddEdge(i,j);
		add(ans,sv.CountPerfectMatching());
	}
	{
		vector<vector<bool>> c(n,vector<bool>(n,false));
		for(auto e:es)
			c[e.first][e.second]=true;
		REP(i,n)
			c[i][i]=true;
		Solver sv(n);
		REP(i,n)REP(j,n)if(c[i][j])
			sv.AddEdge(i,j);
		sub(ans,sv.CountPerfectMatching());
	}
	{
		vector<vector<bool>> c(n,vector<bool>(n,false));
		for(auto e:es)
			c[e.first][e.second]=true;
		REP(i,n)
			c[i][n-1-i]=true;
		Solver sv(n);
		REP(i,n)REP(j,n)if(c[i][j])
			sv.AddEdge(i,j);
		sub(ans,sv.CountPerfectMatching());
	}
	{
		vector<vector<bool>> c(n,vector<bool>(n,false));
		for(auto e:es)
			c[e.first][e.second]=true;
		REP(i,n)
			c[i][i]=true;
		REP(i,n)
			c[i][n-1-i]=true;
		Solver sv(n);
		REP(i,n)REP(j,n)if(c[i][j])
			sv.AddEdge(i,j);
		add(ans,sv.CountPerfectMatching());
	}
	cout<<ans<<endl;
}