#include <stdio.h>

int main() {

    int n;
    scanf("%d", &n);
    int num_triples, num_half;
    num_triples = n / 3;
    num_half = n / 2;

    int num_overlap = 2 * num_triples - num_half;
    long long ans = 1;
    long long mod = 1000000007;

    for (int i = num_triples - num_overlap + 1; i <= num_triples; i++) {
        ans = (ans * i % mod * i) % mod;
    }
    for (int i = n - 2 * num_triples + num_overlap + 1; i <= n - num_triples; i++) {
        ans = (ans * i % mod * i) % mod;
    }
    for (int i = num_overlap + 1; i <= n - 2 * num_triples + num_overlap; i++) {
        ans = (ans * i) % mod;
    }
    printf("%lld", ans);

}

Abbr:

  1. trip: num_triple
  2. over: num_overlap

排列组合公式为：C(trip,over)*A(trip,over)*A(n-trip, trip-over)*A(n-trip,n-trip)

  1. C(trip,over) 下标为3的位置里面挑出 over个位置，后面在这over个位置里放 值为3的，其他下标为3的放 值不为3的
  2. A(trip,over) 从 值为3的 里面挑 over个排序，放刚刚挑出的over个位置上
  3. A(n-trip, trip-over) 从 值不为3的 里面挑 trip-over个排序 放在其他下标为3的位置上
  4. A(n-trip,n-trip) 剩下的排个序

公式列出来消元后简化成3个for循环节省时间