#include<stdio.h>
#include<stdlib.h>
#include<pthread.h>
int position[300]={0},col[100]={0},dig[300]={0},invdig[300]={0},count=0,check[100]={0},thread_count;
pthread_t tid[100];
pthread_mutex_t lock;
struct Posi{
    int x;
	int y;
	int n;
        int p_col[100];
	int p_dig[300];
	int p_invdig[300];
	int p_position[300];
	int thread_id;
};
void nqueen(int n,int row,int n_position[],int n_col[],int n_dig[],int n_invdig[],int which,int x,int y){
	int i,j;
	if(x!=-1 && y!=-1){
		n_col[y]=1;
		n_dig[x-y+n]=1;
		n_invdig[x+y]=1;
		n_position[x]=y;
	}
	if(row==(n+1)){
	/*	for(i=1;i<=n;i++){
			for(j=1;j<=n;j++){
				if(n_position[i]==j)
					printf("o");
				else 
					printf("x");
			}
			printf("\n");
		}
		printf("=========================\n");*/
		pthread_mutex_lock(&lock);
		count++;
		pthread_mutex_unlock(&lock);
		return;
	}
	else if(check[row]==1){
		nqueen(n,row+1,n_position,n_col,n_dig,n_invdig,which,-1,-1);
	}
	else{		
		for(i=1;i<=n;i++){
			if(n_col[i]==0 && n_dig[row-i+n]==0 && n_invdig[i+row]==0){
				n_col[i]=1;
				n_dig[row-i+n]=1;
				n_invdig[i+row]=1;
				n_position[row]=i;
				nqueen(n,row+1,n_position,n_col,n_dig,n_invdig,which,-1,-1);
				n_col[i]=0;
				n_dig[row-i+n]=0;
				n_invdig[i+row]=0;
			}
		}
	}
}
void *parallel(void *k){
	struct Posi *get=(struct Posi*)k;
	nqueen(get->n,get->x+1,get->p_position,get->p_col,get->p_dig,get->p_invdig,get->thread_id,get->x,get->y);
	pthread_exit(NULL); 
}
int gotoparallel(int n){
	int i,j,k,rc;
	struct Posi pos[100];
	for(i=1;i<=n;i++){
		if(check[i]!=1){
			for(j=1;j<=n;j++){
				if(col[j]==0 && dig[i-j+n]==0 && invdig[j+i]==0){
					for(k=1;k<=2*n;k++){
						pos[thread_count].p_col[k]=col[k];
						pos[thread_count].p_dig[k]=dig[k];
						pos[thread_count].p_invdig[k]=invdig[k];
						pos[thread_count].p_position[k]=position[k];
					}
					pos[thread_count].x=i;
					pos[thread_count].y=j;
					pos[thread_count].n=n;
					pos[thread_count].thread_id=thread_count;
					rc=pthread_create(&tid[thread_count],NULL,parallel,(void*)&pos[thread_count]);
					if(rc){
						printf("ERROR; retrun for pthread_create is %d\n",rc);
						exit(-1);
					}
			/*		if(pthread_join(tid[thread_count],NULL)){
						perror("pthread_join");
						return 1;
					}*/
					thread_count++;
				}
			}
			break;
		}
	}
	for(i=0;i<thread_count;i++){
		if(pthread_join(tid[thread_count],NULL)){
			printf("thread join error\n");
		}
	}
	return 0;
}

int main (){
	int n,m,x,y,i;
	thread_count=0;
	scanf("%d %d",&n,&m);
	for(i=0;i<m;i++){
		scanf("%d %d",&x,&y);
		x++;
		y++;
		col[y]=1;
		dig[x-y+n]=1;
		invdig[y+x]=1;
		check[x]=1;	
		position[x]=y;
	}
	gotoparallel(n);
	printf("count=%d\n",count);
	return 0;
}