C++11(clang++ 3.9) 解法, 执行用时: 53ms, 内存消耗: 11716K, 提交时间: 2018-06-09 18:03:55

#include <bits/stdc++.h>
using namespace std;
const int N=1e7+1,MD=1e9+7;
int n,fac[N],inv[N],F[N],ans;
int po(int x,int y)
{
    int t=1;
    for(; y; y>>=1,x=1LL*x*x%MD)
        if(y&1)t=1LL*t*x%MD;
    return t;
}
int main()
{
    scanf("%d",&n);
    fac[0]=1,fac[1]=1,F[0]=1,F[1]=2;
    for(int i=2; i<=n; i++)
    {
        fac[i]=1LL*fac[i-1]*i%MD;
        F[i]=(1LL*F[i-1]*(i+i)-1LL*(i-1)*(i-1)%MD*F[i-2])%MD;
    }
    inv[n]=po(fac[n],MD-2);
    for (int i=n; i; i--)
        inv[i-1]=1LL*inv[i]*i%MD;
    for(int i=0; i<=n; i++)
        ans=(ans+1LL*(i&1?-1:1)*fac[n]*fac[n]%MD*inv[i]%MD*inv[n-i]%MD*inv[n-i]%MD*F[n-i]%MD*F[n-i])%MD;
    printf("%d\n",(ans+MD)%MD);
    return 0;
}