　$N=10000,A=7,B=4$ とする．下二つの条件は次と同値である．
$$(x_{k+1}-x_k,x_{k+2}-x_{k+1})\in\bigl\\{(-1,0),(-1,2),(0,0),(0,2),(1,-1),(1,1),(2,-1),(2,1)\bigr\\}$$
　この条件と $x_1=B$ をみたす整数の組 $(x_1,\dots,x_N)$ を**整った組**と呼ぶこととする．整った組 $(x_1,\dots,x_N)$ に対し，パスカルの三角形において各 $k=1,\dots,N$ について $\dbinom{A+k}{x_k}$ に対応する点を赤色に塗ることを考える．このとき，パスカルの三角形の $A+1$ 行目から $A+N+1$ 行目の各行からうまく一つずつ点を青色に塗り次の条件※をみたすようにできる．

- **条件※** ： $i=A+1,A+2,...,A+N$ について，$i$ 行目の赤色に塗られた点（赤点）と青色に塗られた点（青点）は隣り合っており，その2点のちょうど下に $i+1$ 行目の青点がある．

　隣接する行の青点をつなげた折れ線を**道**と呼ぶこととする．$\dbinom{A+1}{B}$ が赤点となるような道を一つ固定したとき，条件※を満たす青点の集合を与えるような整った組はただ一つ存在することが確認できる．すなわち $\dbinom{A+1}{B}$ が赤点となるような道と整った組は1対1で対応する．
<details>
<summary>図：$N=10$ の場合の点・道の例<\/summary>
　赤点をバツ，青点をマルで表している．
![figure 1](\/images\/E8s6hWDwbGw5fbT8M8jGpmMKgs6AbOd3UT7tvxEK)
<\/details>

　ここで端点が $\dbinom{A+1}{i},\dbinom{A+N+1}{j}$ に対応する道および，それに対応する赤点に対応する組 $(x_1,\dots,x_N)$ について，二項係数の計算により次が成り立つことがわかる．
$$\sum_{k=1}^{N}\binom{A+k}{x_k}=\binom{A+N+1}{j}-\binom{A+1}{i}$$

　$\dbinom{A+1}{B}$ が赤点となるような道の $A+1$ 行目の青点としてありうるのは $\dbinom{A+1}{B-1}$ または $\dbinom{A+1}{B +1}$ である．前者の場合，$A+N+1$ 行目の青点としてありうるのは $\dbinom{A+N+1}{B+i}\ (i=0,1,\dots,N-1)$ であり，それぞれ対応する道は $\dbinom{N-1}{i}$ 通りあるため求める値への寄与は
$$\sum_{i=0}^{N-1}\binom{N-1}{i}\Biggl(\binom{A+N+1}{B+i}-\binom{A+1}{B-1}\Biggr)=\binom{A+2N}{N+B-1}-2^{N-1}\binom{A+1}{B-1}.$$

後者の場合，$A+N+1$ 行目の青点としてありうるのは $\dbinom{A+N+1}{B+1+i}\ (i=0,1,\dots,N-1)$ であり，それぞれ対応する道は $\dbinom{N-1}{i}$ 通りあるため求める値への寄与は
$$\sum_{i=0}^{N-1}\binom{N-1}{i}\Biggl(\binom{A+N+1}{B+1+i}-\binom{A+1}{B+1}\Biggr)=\binom{A+2N}{N+B}-2^{N-1}\binom{A+1}{B+1}.$$

よって求める総和 $X$ は次のように計算できる．
$$X=\binom{A+2N+1}{N+B}-2^{N-1}\Biggl(\binom{A+1}{B-1}+\binom{A+1}{B+1}\Biggr)$$
特に $N=10000,A=7,B=4$ のとき $X$ を $20011$ で割ったあまりは次のように計算できる．

$$\begin{aligned}
X
&=\dbinom{20008}{10004}-7\cdot2^{10003}\\\\
&\equiv\frac{(-3)(-4)\cdots(-10006)}{10004!}-\frac{7}{4}\times 2^{\frac{20011-1}{2}}\\\\
&\equiv\frac{1}{2}\times\frac{20011-1}{2}\times\frac{20011+1}{2}-\frac{7}{4}\times (-1)^{\frac{20011^2-1}{8}}\\\\
&\equiv\frac{13}{8}\\\\
&\equiv \bm{2503}\pmod{20011}
\end{aligned}$$
公式解説
https://onlinemathcontest.com/contests/omc168/editorial/5006
$$X=\sum_{k=1}^{10000}\sum_{l=-\infty}^{\infty}\Big(x_k=lとなる整数の組の個数\Big)\times\binom{7+k}{l}$$
であるから, $x_k=l$ となる整数の組の個数を求めていく.\
$x_{k+1}-x_k\in \\{-1,1,0,2\\}$ と $2x\_{k+2}−x \_{k+1}−x\_k\in\\{−1,0,3,4\\}$ より以下が成り立つ.
$$x_{k+1}\in\\{x_k-1,x_k\\}\Rightarrow x_{k+2}\in\\{x_{k+1},x_{k+1}+2\\},$$
$$x_{k+1}\in\\{x_k+1,x_k+2\\}\Rightarrow x_{k+2}\in\\{x_{k+1}-1,x_{k+1}+1\\},$$
$k\geq2$ について, \
$x_k\in\\{x_{k-1}-1,x_{k-1}\\}$ かつ $x_k=l$ となる $(x_1,x_2,\dots,x_k)$ としてありうるものの個数を $a_{k,l}$,\
 $x_k\in\\{x_{k-1}+1,x_{k-1}+2\\}$ かつ $x_k=l$ となる $(x_1,x_2,\dots,x_k)$ としてありうるものの個数を $b_{k,l}$ とすると, 以下が成立.

- $a_{2,3}=a_{2,4}=b_{2,5}=b_{2,6}=1$.
- $k\geq3$ について $a_{k,l}=a_{k-1,l}+b_{k-1,l+1}$.
- $k\geq3$ について $b_{k,l}=a_{k-1,l-2}+b_{k-1,l-1}$.

　これから帰納的に$k\geq2$ について以下が成立すること分かる.
$$a_{k,l}=\binom{k-1}{l-3},\quad b_{k,l}=\binom{k-1}{l-5}$$

 $(x_1,x_2,\dots,x_k)$ を固定したとき $(x_1,x_2,\dots,x_{10000})$ のとりうる整数組の個数は, $2^{10000-k}$ であるから, $k\geq2$ について,
$$
\begin{aligned}
\Big(x_k=lとなる整数の組の個数\Big)
&=(a_{k,l}+b_{k,l})\times 2^{10000-k}\\\\
&=\Bigg(\binom{k-1}{l-3}+\binom{k-1}{l-5}\Bigg)2^{10000-k}
\end{aligned}$$ 
個である. したがって $k (\geq2)$ について
$$
\begin{aligned}
&\sum_{l=-\infty}^{\infty}\Big(x_k=lとなる整数の組の個数\Big)\times\binom{7+k}{l}\\\\
=&\sum_{l=-\infty}^{\infty}\Bigg(\binom{k-1}{l-3}+\binom{k-1}{l-5}\Bigg)2^{10000-k}\times\binom{7+k}{7+k-l}\\\\
=&2^{10000-k}\sum_{l=-\infty}^{\infty}\Bigg(\binom{k-1}{l-3}\binom{7+k}{k+4-(l-3)}+\binom{k-1}{l-5}\binom{7+k}{k+2-(l-5)}\Bigg)\\\\
=&2^{10000-k}\Bigg(\binom{2k+6}{k+4}+\binom{2k+6}{k+2}\Bigg)\\\\
=&2^{10001-k}\binom{2k+6}{k+2}
\end{aligned}$$
　したがって,$$X=\binom{8}{4}\times4\times2^{9998}+\sum_{k=2}^{10000}2^{10001-k}\binom{2k+6}{k+2}$$
　ここで以下の補題を紹介する.
----
**補題.**
$$\sum_{k=0}^{N}2^{N-k}\binom{2k}{k-1}=\frac{1}{2}\binom{2(N+1)}{N+1}-2^{N}$$.

**証明**\
　$f(x)=\sum_{k=0}^{\infty}\binom{2k}{k-1}x^k$とする. このとき以下が成立する.(参照:[OMCE002-F解説
](https:\/\/onlinemathcontest.com\/contests\/omce002\/editorial\/8694))
$$\begin{aligned}
f(x)&=\sum_{k=0}^{\infty}\binom{2k}{k-1}x^k\\\\
&=x\sum_{k=0}^{\infty}\binom{2k+2}{k}x^k\\\\
&=x\Bigg(\sum_{k=0}^{\infty}\frac{1}{k+1}\binom{2k}{k}x^k\Bigg)^2\Bigg(\sum_{k=0}^{\infty}\binom{2k}{k}x^k\Bigg)\\\\
&=x\Bigg(\frac{1-\sqrt{1-4x}}{2x}\Bigg)^2\Bigg(\frac{1}{\sqrt{1-4x}}\Bigg)\\\\
&=\dfrac{1}{2x}\Bigg(\dfrac{1-2x}{\sqrt{1-4x}}-1\Bigg).
\end{aligned}$$
　$\sum_{k=0}^{N}2^{N-k}\binom{2k}{k+1}$ は$$\dfrac{1}{1-2x}f(x)=\dfrac{1}{2x}\Bigg(\dfrac{1}{\sqrt{1-4x}}-\dfrac{1}{1-2x}\Bigg)$$ における $x^N$ の係数であるから,
$$
\begin{aligned}
\sum_{k=0}^{N}2^{N-k}\binom{2k}{k+1}&=[x^N]\frac{1}{2x}\Bigg(\frac{1}{\sqrt{1-4x}}-\frac{1}{1-2x}\Bigg)\\\\
&=\frac{1}{2}\Bigg([x^{N+1}]\frac{1}{\sqrt{1-4x}}-[x^{N+1}]\frac{1}{1-2x}\Bigg)\\\\
&=\frac{1}{2}\binom{2(N+1)}{N+1}-2^{N}
\end{aligned}
$$
----
　したがって,
$$
\begin{aligned}
X&=\binom{8}{4}\times4\times2^{9998}+\sum_{k=2}^{10000}\binom{2k+6}{k+4}2^{10001-k}\\\\
&=\binom{8}{4}\times2^{10002}+2\sum_{k=5}^{10003}\binom{2k}{k+1}2^{10003-k}\\\\
&=\binom{8}{4}\times2^{10002}+2\Big(\frac{1}{2}\binom{20008}{10004}-2^{10003}-\sum_{k=0}^{4}\binom{2k}{k+1}2^{10003-k}\Big)\\\\
&=\binom{8}{4}\times2^{10002}+\binom{20008}{10004}-2^{10004}-\sum_{k=0}^{4}\binom{2k}{k+1}2^{10004-k}\\\\
\end{aligned}
$$
ユーザー解説
https://onlinemathcontest.com/contests/omc168/editorial/5006/626
　次の条件をすべてみたす $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$$