题解 | 小红的好排列

import sys

MOD = 10**9 + 7


def precompute_factorials(n):
    fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i - 1] * i % MOD
    return fact


def mod_inv(x):
    return pow(x, MOD - 2, MOD)


def precompute_inv_factorials(n, fact):
    inv_fact = [1] * (n + 1)
    inv_fact[n] = mod_inv(fact[n])
    for i in range(n - 1, -1, -1):
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD
    return inv_fact


def comb(n, k, fact, inv_fact):
    if k < 0 or k > n:
        return 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD


def solve():
    n = int(sys.stdin.readline().strip())
    d = n // 3  # 3的倍数的数字个数和位置个数
    m = n // 2 - d  # 需要分配3的倍数到非3倍数位置的个数
    if m < 0 or m > d:
        print(0)
        return

    # 预计算阶乘和逆阶乘
    fact = precompute_factorials(n)
    inv_fact = precompute_inv_factorials(n, fact)

    # 计算组合数
    c1 = comb(d, m, fact, inv_fact)
    c2 = comb(n - d, m, fact, inv_fact)

    # 计算答案
    ans = c1 * c2 % MOD
    ans = ans * fact[d] % MOD
    ans = ans * fact[n - d] % MOD
    print(ans)


if __name__ == "__main__":
    solve()