BZOJ3028 食物

$$ \text{每种食物搞一个生成函数。} \\ \text{承德汉堡:}\frac{1}{1-x^2}=1+x^2+x^4+x^6…. \\ \text{可乐:}\left( \begin{array}{c} \begin{array}{c} 1+x\\ \end{array}\\ \end{array} \right) \\ \text{鸡腿:}\left( 1+x+x^2 \right) \\ \text{蜜桃多:}\frac{x}{1-x^2}=x+x^3+x^5+x^7+… \\ \text{鸡块:}\frac{1}{1-x^4}=1+x^4+x^8+x^{12}+… \\ \text{包子:}\left( 1+x+x^2+x^3 \right) \\ \text{土豆片炒肉:}\left( 1+x \right) \\ \text{面包:}\frac{1}{1-x^3}=1+x^3+x^6+x^9+…. \\ \text{乘起来得到} \\ \frac{x\left( 1+x \right) ^2\left( 1+x+x^2 \right) \left( 1+x+x^2+x^3 \right)}{\left( 1-x^2 \right) ^2\left( 1-x^4 \right) \left( 1-x^3 \right)}=\frac{x\left( 1+x \right) ^2\left( 1+x+x^2 \right) \left( 1+x+x^2+x^3 \right)}{\left( 1-x \right) ^2\left( 1+x \right) ^2\left( 1+x^2 \right) \left( 1-x^2 \right) \left( 1-x^3 \right)} \\ =\frac{x\left( 1+x+x^2 \right) \left( 1+x+x^2+x^3 \right)}{\left( 1-x \right) ^2\left( 1+x^2 \right) \left( 1-x^2 \right) \left( 1-x^3 \right)} \\ \text{由立方差公式可得}\left( 1-x^3 \right) =\left( 1-x \right) \left( 1+x+x^2 \right) \\ \text{故原式}=\frac{x\left( 1+x+x^2+x^3 \right)}{\left( 1-x \right) ^3\left( 1+x^2 \right) \left( 1-x^2 \right)}=\frac{x\left( 1+x+x^2+x^3 \right)}{\left( 1-x \right) ^4\left( 1+x^2 \right) \left( 1+x \right)}=\frac{x\left( 1+x+x^2+x^3 \right)}{\left( 1-x \right) ^4\left( 1+x+x^2+x^3 \right)}=\frac{x}{\left( 1-x \right) ^4} \\ \text{根据广义二项式级数，则有}\frac{1}{\left( 1-x \right) ^k}=\sum_{i\ge 0}{\left( \begin{array}{c} i+k-1\\ i\\ \end{array} \right) x^i,\text{则有}\frac{x}{\left( 1-x \right) ^4}=\sum_{i\ge 0}{\left( \begin{array}{c} i+2\\ i-1\\ \end{array} \right)}x^i} \\ \text{故答案为}\left( \begin{array}{c} n+2\\ n-1\\ \end{array} \right) ,\text{卢卡斯定理即可。} \\ \text{也可}\left( \begin{array}{c} n+2\\ n-1\\ \end{array} \right) =\frac{\left( n+2 \right) \left( n+1 \right) n}{\text{3!}} $$

mod = 10007
fact = [1]
for i in range(1, mod):
    fact.append(fact[-1]*i % mod)


def C(n, m):
    if n < m:
        return 0
    return fact[n]*pow(fact[m]*fact[n-m], mod-2, mod) % mod


n = int(input())


def Cx(n, m):
    if n < m:
        return 0
    if m == 0:
        return 1
    return Cx(n//mod, m//mod)*C(n % mod, m % mod) % mod


print(Cx(n+2, n-1))