#include <cstdio>
#include <algorithm>
using namespace std;
 
const int MOD = 55566677;
 
int n,m,x[25],y[25];
int day[60],chp[60],s[60]={1};
 
int dfs(int i, int t){
    if(i==m){
        if(t%2) return (MOD-s[n-t])%MOD; else
                return s[n-t];
    }
    int ret=dfs(i+1,t);
    if(!day[x[i]] && !chp[y[i]]){
        day[x[i]]=chp[y[i]]=1;
        ret=(ret+dfs(i+1,t+1))%MOD;
        day[x[i]]=chp[y[i]]=0;
    }
    return ret;
}
 
int main(){
    for(int i=1;i<60;i++) s[i]=s[i-1]*1ll*i%MOD;
    while(scanf("%d%d",&n,&m)==2){
        for(int i=0;i<m;i++) scanf("%d%d",x+i,y+i);
        for(int i=0;i<m;i++) for(int j=i+1;j<m;j++){
            if(x[i]==x[j] && y[i]==y[j]){
                swap(x[j],x[m-1]);
                swap(y[j],y[--m]);
            }
        }
        printf("%d\n",dfs(0,0));
    }
}
 

I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPGFsZ29yaXRobT4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCmNvbnN0IGludCBNT0QgPSA1NTU2NjY3NzsKCmludCBuLG0seFsyNV0seVsyNV07CmludCBkYXlbNjBdLGNocFs2MF0sc1s2MF09ezF9OwoKaW50IGRmcyhpbnQgaSwgaW50IHQpewogICAgaWYoaT09bSl7CiAgICAgICAgaWYodCUyKSByZXR1cm4gKE1PRC1zW24tdF0pJU1PRDsgZWxzZQogICAgICAgICAgICAgICAgcmV0dXJuIHNbbi10XTsKICAgIH0KICAgIGludCByZXQ9ZGZzKGkrMSx0KTsKICAgIGlmKCFkYXlbeFtpXV0gJiYgIWNocFt5W2ldXSl7CiAgICAgICAgZGF5W3hbaV1dPWNocFt5W2ldXT0xOwogICAgICAgIHJldD0ocmV0K2RmcyhpKzEsdCsxKSklTU9EOwogICAgICAgIGRheVt4W2ldXT1jaHBbeVtpXV09MDsKICAgIH0KICAgIHJldHVybiByZXQ7Cn0KCmludCBtYWluKCl7CiAgICBmb3IoaW50IGk9MTtpPDYwO2krKykgc1tpXT1zW2ktMV0qMWxsKmklTU9EOwogICAgd2hpbGUoc2NhbmYoIiVkJWQiLCZuLCZtKT09Mil7CiAgICAgICAgZm9yKGludCBpPTA7aTxtO2krKykgc2NhbmYoIiVkJWQiLHgraSx5K2kpOwogICAgICAgIGZvcihpbnQgaT0wO2k8bTtpKyspIGZvcihpbnQgaj1pKzE7ajxtO2orKyl7CiAgICAgICAgICAgIGlmKHhbaV09PXhbal0gJiYgeVtpXT09eVtqXSl7CiAgICAgICAgICAgICAgICBzd2FwKHhbal0seFttLTFdKTsKICAgICAgICAgICAgICAgIHN3YXAoeVtqXSx5Wy0tbV0pOwogICAgICAgICAgICB9CiAgICAgICAgfQogICAgICAgIHByaW50ZigiJWRcbiIsZGZzKDAsMCkpOwogICAgfQp9Cg==