组合数学（Python）

参考：https://blog.nowcoder.net/n/0fd8dbf5108c4ebda0ae48f8b43f3ba6

思路：组合数学，推式子。这种组合数学比较常用的就是fac预处理以及乘法逆元inv和comb的函数了，要写熟。然后就是数学过程的推式子了，令表示中有多少个位置是3的倍数，同时也表示排列中有多少个数是3的倍数；再令表示我们最终需要的3的倍数位置个数。

n其实可以分成两组数据，一组为3的倍数，一组为不是3的倍数。那么答案就是先表示需要从cnt个3的倍数中选出除去3的倍数位置外，额外需要的3的倍数，他们的方案数，要把他们放到外面（不是3的倍数位置）；然后再表示从不是3的倍数中选出和刚才放到外面的3的倍数相同的不是3的倍数的数量，他们的方案数，要把他们放到里面（是3的倍数位置）；最后再各自分别表示里面和外面元素的全排列，因此答案为

代码：

import sys
from itertools import permutations

input = lambda: sys.stdin.readline().strip()

import math
inf = 10 ** 18

def I():
    return input()

def II():
    return int(input())

def MII():
    return map(int, input().split())

def GMI():
    return map(lambda x: int(x) - 1, input().split())

def LI():
    return input().split()

def LII():
    return list(map(int, input().split()))

def LFI():
    return list(map(float, input().split()))

fmax = lambda x, y: x if x > y else y
fmin = lambda x, y: x if x < y else y
isqrt = lambda x: int(math.sqrt(x))

'''

'''

mod = 10 ** 9 + 7
MAXN = 10 ** 6
fac = [1] * (MAXN + 1)
for i in range(2, MAXN + 1):
    fac[i] = fac[i - 1] * i % mod

def inv(x):
    return pow(x, mod - 2, mod)

def comb(a, b):
    if a < b:
        return 0
    return fac[a] * inv(fac[b]) * inv(fac[a - b]) % mod

def solve():
    n = II()

    if n == 2:
        print(0)
        return

    cnt = n // 3
    need = n // 2
    ans = comb(cnt, need - cnt) * comb(n - cnt, need - cnt) * fac[cnt] * fac[n - cnt]
    print(ans % mod)

t = 1
# t = II()
for _ in range(t):
    solve()