一个位置如果是有效的，那么要么位置是3的倍数，要么数字是3的倍数。

记有cnt =\lfloor \frac n 3 \rfloor 个位置和数字是3的倍数。

现在3的倍数已经产生了cnt 个有效计数。

现在我们每分配一个3的位置给3的倍数，有效计数就不变，我们每分配一个3的位置给非3的倍数，有效计数就+1

只需要保证最后的计数是\frac n 2即可。

假设分了一一对应的位置给3的倍数有k 个，这k 个位置没有任何贡献

为了凑足\frac n 2 ，此时还有剩余cnt-k 个位置没安排，还需要选 \frac n2 -cnt 个计数。

显然当cnt-k=\frac n2 -cnt 时为恰好，此时算出 k=2cnt-\frac n 2 。

也就是固定死了的位置只有k+(\frac n 2 -cnt)=cnt 个，剩余n-cnt 可以自由排列。

同时，前面k个位置，我们并没有指定k 是哪几个位置，我们可以将cnt 进行全排列，按序分配，这样就避免了讨论。

\mathrm{C_{cnt}^k\times C_{n-cnt}^{\frac n 2-cnt}\times (n-cnt)! \times cnt!}

在实现上用卢卡斯定理即可。

#include <iostream>

using namespace std;
const int N=1e6+7;
const int p=1e9+7;
typedef long long LL;
LL pre[N];
LL qmi(LL a,int k, int p)
{
    LL res = 1;
    while(k)
    {
        if(k & 1) res = res * a % p;
        k >>= 1;
        a = a * a % p;
    }
    return res;
}

int C(int a,int b,int p)
{
    if(a < b) return 0;

    LL res = 1;
    for(int i = 1, j = a; i <= b; i ++ , j -- )
    {
        res = res * j % p;
        res = res * qmi(i, p - 2, p) % p;
    }
    return res;
}

LL lucas(LL a, LL b, int p)
{
    if(a < p && b < p) return C(a, b, p);
    return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}


int main()
{
    int n;
    cin >> n;
    pre[1]=1;
    for(int i=2;i<=n;i++)pre[i]=(pre[i-1]*i)%p;
    LL cnt=n/3;
    LL k=2*cnt-n/2;
    LL ans=lucas(cnt,k,p);
    ans=(ans * lucas(n-cnt,n/2-cnt,p)) %p;
    ans=(ans * pre[n-cnt])%p;
    ans=(ans * pre[cnt])%p;
    cout<<ans;
    return 0;
}