OMC168(F)

点数: 800

Writer: natu_math

　次の条件をすべてみたす $10000$ 個の整数の組 $(x_1,x_2,...,x_{10000})$ を考えます：

• $x_1=4$．
• $k = 1,2,\ldots,9999$ について $x_{k+1}-x_k\in\{-1,0,1,2\}$．
• $k = 1,2,\ldots,9998$ について $2x_{k+2}-x_{k+1}-x_k\in\{-1,0,3,4\}$．

そのような組としてありうるものすべてに対して，次の値を足し合わせたものを $X$ とします： $$\sum_{k=1}^{10000}{}_{7+k}\mathrm{C}_{x_k}$$ $X$ を素数 $20011$ で割った余りを求めてください．
　なお，奇素数 $p$ に対して，以下が成り立つことを用いて構いません： $$2^{\frac{p-1}{2}}\equiv(-1)^{\frac{p^2-1}{8}}\pmod p$$