题解 | 小红的好排列

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e6+10;
const ll mod = 1e9+7;
ll n;
ll pw[N];

ll qpow(ll a,ll b,ll p)
{
    ll res = 1;
    for(;b;b>>=1)
    {
        if(b&1)
        {
            res = res*a%p;
        }
        a = a*a%p;
    }
    return res;
}


ll C(ll a,ll b)
{
    return pw[a]*qpow(pw[b],mod-2,mod)%mod*qpow(pw[a-b],mod-2,mod)%mod;
}

void solve()
{
    cin>>n;
    if(n<=2)
    {
        cout<<0<<'\n';
        return ;
    }
    ll a = n/3*2-n/2;
    ll b = n-n/3;
    ll c = n/3;

    ll res = C(c,a)*C(b,c-a)%mod*pw[n/3]%mod*pw[n-n/3]%mod;
    // cout<<cnt1<<' '<<cnt2<<' '<<C(cnt2,cnt1)<<' '<<pw[cnt2]<<' '<<pw[cnt1]<<'\n';

    cout<<res<<'\n';


//1905120
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    pw[0]=1;
    for(ll i=1;i<=N-1;i++)
    {
        pw[i]=pw[i-1]*i%mod;
    }
    int t=1;
    // cin>>t;
    while(t--)
    {
        solve();

    }


    return 0;
}