题解 | 小红的好排列

这涉及数学的排列组合，首先，我们知道，两数只要有一个数是三的倍数，那么他们的积也是3的倍数

分为两种情况，当n = 2时是绝对不能满足条件的

当n是大于2的偶数，是3的倍数数字的个数和是3倍数位置的个数错开是完全可以大于总数的一半的

对于第二种情况，我们使用排列组合，先考虑3倍数重叠部分，再考虑不能重叠的部分，然后考虑剩下的部分

最终，把3个部分相乘即可得到答案

因为结果要取模，要懂得运用费马小定理和模拟元的知识，自定义排列，组合，阶乘的函数

mod = 1000000007
# 阶乘
def my_fac(n):
    ans = 1
    for i in range(1, n + 1):
        ans = (ans * i) % mod
    return ans
# 组合运算
def my_comb(n, k):
    nr = my_fac(n)
    dr = (my_fac(k) * my_fac(n - k)) % mod
    inv_dr = pow(dr, mod - 2, mod)
    return (nr * inv_dr) % mod
# 排列运算
def my_perm(n, k):
    nr = my_fac(n)
    dr = my_fac(n - k)
    inv_dr = pow(dr, mod - 2, mod)
    return (nr * inv_dr) % mod

n = int(input())
# 统计3的倍数数量
b = n // 3
# 统计一半数量
c = n // 2
if n == 2:
    print(0)
else:
    # 3倍相交部分
    res = my_comb(b, 2 * b - c) % mod; res = (res * my_perm(b, 2 * b - c)) % mod
    # 3倍不相交部分
    res = (res * my_perm(n - b, c - b)) % mod
    # 剩余部分
    res = (res * my_perm(n - b, n - b)) % mod
    print(res)