题解 | 小红的好排列

def ksm(a, b):  # 快速幂  计算 a ** b
    res = 1
    while b:
        if b & 1:
            res = res * a % MOD
        a = a * a % MOD
        b >>= 1
    return res
 

def cal_c(n, m):      # 计算组合数C n m 
    if m > n - m:   
        m = n - m
    ans = 1
    for i in range(1, m+1):
        ans = ans * (n - m + i) * ksm(i, MOD - 2) % MOD
    return ans


 def cal_a(n, m):    # 计算排列数 A n m
    ans = 1
    for i in range(1, m+1):
        ans = ans * (n + 1 - i) % MOD
    return ans


while True:
    try:
        n = int(input())
        k = n // 3      # 有k个位置和k个数是3的倍数
        s = n // 2 - k  # 这s个位置上放的数必须是3的倍数
        m = n - k   # m个位置和m个数不是3的倍数
        MOD = 10 ** 9 + 7
        if s < 0 or s > k:
            print(0) 
        else:
            # 从m个位置中选s个位置放3的倍数
            ans = cal_c(m, s)
            # 从k个3的倍数中选s个数，全排列，放到上面s个位置中
            ans = ans * cal_a(k, s) % MOD
            # 剩余的k-s个3的倍数必须放在那k个位置中，全排列
            ans =  ans * cal_a(k, k-s) % MOD
            # 剩余的m个数全排列
            ans = ans * cal_a(m, m) % MOD

            print(ans)
    except:
        break