分析

看到这道题断定就是一个简单的圆排列问题
但由于我们不知道有几对情侣会在一起
那么我们求一个补问题
枚举坐在一起的情侣的对数
再进行简单容斥即可
容易推出公式:

由于本题需要的是的时间复杂度
所以我们需要对于每个组合数求得
Fac[]表示前缀积
Inv[]表示前缀积的逆元
那么

即可解决这个问题

代码

//Newcoder 19857
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>

#define LL long long
#define FOR(i,A,B) for(LL i=A;i<=B;i++)
#define BOR(i,A,B) for(LL i=A;i>=B;i--)
using namespace std;
const int MaxN=6e7+10;
const LL Mod=1e9+7,Temp=500000004;

int Inv[MaxN]={1};
LL Fac=1,Ans,Two=1,Tot;
LL Total;

inline LL Fast(LL A,LL B) {
    LL Res=1;
    while(B) {
        if(B & 1) Res=(Res*A)%Mod;
        A=(A*A)%Mod; B>>=1;
    }
    return Res%Mod;
}

int main() {
    scanf("%lld",&Total);
    if(Total==1) { cout<<"0"<<endl; return 0; }
    FOR(i,1,Total) { Two=Two*2%Mod; Fac=Fac*i%Mod; }
    Tot=Fac*Fast(Total,Mod-2)%Mod;
    Inv[Total]=Fast(Fac,Mod-2);
    BOR(i,Total-1,0) { Inv[i]=1ll*Inv[i+1]*(i+1)%Mod; } 
    BOR(i,Total,0) {    
        Ans=(Ans+Tot*Two%Mod*1ll*Inv[i]%Mod*Inv[Total-i]%Mod*(i & 1 ? -1 : 1))%Mod;
        Two=Two*Temp%Mod;
        Tot=Tot*(2*Total-i)%Mod;
    }
    Ans=(Ans+Mod)%Mod;
    Ans=Ans*Fac%Mod;
    printf("%lld\n",Ans); 
    system("pause");
    return 0;
}