In Chinese Restaurant

题目连接：

Description

When Vova arrived in Guangzhou, his Chinese friends immediately invited him to a restaurant. Overall n people came to the restaurant, including Vova. The waiter offered to seat the whole company at a traditional large round table with a rotating dish plate in the center.

As Vova was a guest, he got the honorable place by the door. Then m people in the company stated that they wanted to sit near a certain person. Your task is to determine the number of available arrangements to seat Vova's friends at the table.

Input

The first line contains integers n and m (2 ≤ n ≤ 100; 0 ≤ m ≤ n). The next m lines contain integers k1, …, km, where ki is the number of the person who the person number i wants to sit with (1 ≤ ki ≤ n; ki ≠ i). Being an honorable guest, Vova got number 1. His friends are numbered with integers from 2 to n.

Output

Print the number of available arrangements to seat Vova's friends modulo 10 9 + 7.

Sample Input

6 6

2

1

1

5

6

5

Sample Output

4

Hint

题意

有n个人在坐在一个圆桌上，给你m个关系a,b,表示a要挨着b坐

问你有多少个方案数

题解：

如果出现环，答案为2，否则就是全排列乘以2

特判掉 只有两个人的情况，因为这样正着坐和反着坐答案是一样的。

代码

#include 
    
     #define rep(a,b,c) for(int (a)=(b);(a)<=(c);++(a))#define drep(a,b,c) for(int (a)=(b);(a)>=(c);--(a))#define pb push_back#define mp make_pair#define sf scanf#define pf printf#define two(x) (1<<(x))#define clr(x,y) memset((x),(y),sizeof((x)))#define dbg(x) cout << #x << "=" << x << endl;const int mod = 1e9 + 7;int mul(int x,int y){return 1LL*x*y%mod;}int qpow(int x , int y){int res=1;while(y){if(y&1) res=mul(res,x) ; y>>=1 ; x=mul(x,x);} return res;}inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}return x*f;}using namespace std;const int maxn = 1e3 + 15;vector
     
      G[maxn],block[maxn];int n , m ,vis[maxn] , c[maxn],tot,sz[maxn],deg[maxn],fac[maxn],C[maxn][maxn],moo[maxn][maxn];set < int > Edge[maxn];void maintain(int & x){    if( x >= mod ) x-= mod;}bool dfs1( int x , int pre ){    c[x] = 1;    for(auto v:G[x]){        if( v == pre ) continue;        if(c[v] == 1) return true;        else if(c[v] == 0){            if(dfs1(v,x)) return true;        }    }    c[x] = 2;    return false;}void predfs( int x ){    block[tot].pb( x );    for(auto v : G[x])        if( vis[v] == 0 ){            vis[v] = 1;            predfs( v );        }}void init(){    fac[0] = 1;    C[0][0] = 1;    rep(i,1,maxn-1){        fac[i] = mul( fac[i - 1] , i );        C[i][0] = 1;        rep(j,1,i){            C[i][j] = C[i][j - 1] + C[i - 1][j - 1] ;            maintain( C[i][j] );        }    }}int main(int argc,char *argv[]){    init();    n=read(),m=read();    if(n == 2 && m >= 1 ){        pf("1\n");        return 0;    }    rep(i,1,n) G[i].clear();    rep(i,1,m){        int v=read();        Edge[i].insert( v );        moo[i][v]=moo[v][i]=1;    }    rep(i,1,n){        rep(j,1,n) if( moo[i][j]  && i != j ) G[i].pb( j );    }    int ok = 0;    rep(i,1,n) if(c[i] == 0){        if( dfs1( i , 0 ) ){            ok = 1;            break;        }    }    rep(i,1,n) if(!vis[i]){        vis[i]=1;        ++ tot;        predfs( i );    }    // 有三条边或以上    rep(i,1,n){        int kk = 0;        rep(j,1,n) if( moo[i][j]) ++ kk;        if( kk > 2 ){            pf("0\n");            return 0;        }    }    if( ok ){        if( tot == 1 ){            int judge = 1;            rep(i,1,n) if(c[i] != 1) judge = 0;            if( judge == 1 ) pf("%d\n" , 2);            else pf("0\n");        }else pf("0\n");        return 0;    }else{        int ptr = 0 ;        rep(i,1,tot){            for(auto it : block[i]){                if( it == 1 ){                    ptr = i;                }            }        }        int ans = 1 ;        if( block[ptr].size() > 1 ) ans = 2;        rep(i,1,tot){            if( i == ptr ) continue;            int cap = block[i].size();            if( cap > 1 ) ans = mul( ans , 2 );        }        ans = mul( ans , fac[ tot - 1 ] );        pf("%d\n" , ans );    }    return 0;}