　本コンテストは，当 F 問題の出題ミスにより Unrated となりました．みなさまの貴重なお時間を奪う結果となってしまい，申し訳ありませんでした．詳細は[アナウンス](https:\/\/onlinemathcontest.com\/announcements\/show\/46)をご覧ください．\
　以下の解説は，コンテスト終了の数時間後にユーザーの [MARTH](https:\/\/onlinemathcontest.com\/users\/marth) 氏により [Mathlog](https:\/\/mathlog.info\/articles\/DWsS96nCLHF8ZjHkYKeP) 上に執筆されたものであり，MARTH 氏のご厚意により OMC 上の解説へ移植されたものです．ただし，一部解説の体裁を変更した部分があります．\
　なお，本来想定されていた問題文・解説もユーザー解説に収録されていますので，ご確認いただけると幸いです．

------
　$N=9000,M=8998$ とし，$x,y$ の $2$ 変数冪級数を用いて考える．$i$ 番目のカタラン数 $C_i = \dfrac{1}{i+1}\dbinom{2i}{i}$ を用いて，$x$ の冪級数 $g$ を以下のように定義する：
$$g(x)=\sum_{i=0}^{\infty}C_ix^i$$
このとき，以下が成り立つ：
$$f(x,y)=\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}\binom{2i+4j}{i} x^iy^j=\frac{1}{\sqrt{1-4x}}\frac{1}{1-g(x)^4 y}$$


**証明．** $(0,0)$ から出発し，$y=x+k$ 上のある点 $P(s,s+k)$ へと $x,y$ いずれかの正方向に $1$ 進むことを繰り返して得られる経路について考える．

![figure 1](\/images\/KLFoFZRXzk7BBvwi0M12qcv8pUAa8EcxZsUySmuZ)

　上図のように，$y-x$ が $1$ 増えるごとに経路を分割する（これは一意である）と，経路数について以下の等式を得る：
$$\dbinom{2s+k}{s} = \sum_{n_1+n_2+\dots+n_{k+1}=s}C_{n_1}C_{n_2}\cdots C_{n_k}\binom{2n_{k+1}}{n_{k+1}}$$
したがって,
$$\sum_{i=0}^{\infty}\binom{2i+k}{i}x^i=\left(\sum_{i=0}^{\infty}C_ix^i\right)^k\left(\sum_{i=0}^{\infty}\binom{2i}{i}x^i\right)$$
を得る．また，
$$\sum_{i=0}^{\infty}\binom{2i}{i}x^i=\frac{1}{\sqrt{1-4x}}$$ 
であるから，
$$\sum_{i=0}^{\infty}\binom{2i+k}{i}x^i=\frac{(g(x))^k}{\sqrt{1-4x}}$$
となる．したがって，
$$
\begin{aligned}
f(x, y)&=\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}\binom{2i+4j}{i} x^iy^j\\\\
&=\sum_{j=0}^{\infty}\frac{(g(x))^{4j}}{\sqrt{1-4x}} ~ y^j\\\\
&=\frac{1}{\sqrt{1-4x}}\frac{1}{1-g(x)^4y}\\\\
\end{aligned}
$$
より示すべき等式を得る．$\square$
---

　以降では，簡単のために $f(x,y), g(x)$ を単に $f, g$ と表す（引数はつねに $(x, y), x$ であることに注意）．$S_n$ は $f$ の積のある係数となるが，問題で与えられた制約がいくつかあることに留意しよう．制約 $a_k\neq0$ $(k=1,n)$ については $f$ を $f-\frac{1}{1-y}$ に変えることで，また制約 $(a_k,b_k)\neq(0,0)$ $(k\neq1,n)$ については $f$ を $f-1$ に変えることで対応できる．よって $S_n$ は，
$$\bigg(f-\frac{1}{1-y}\bigg)(f-1)^{n-2}\bigg(f-\frac{1}{1-y}\bigg)$$
の $x^{N}y^{M}$ の係数となり，$\displaystyle \sum_{n=2}^{\infty}(-1)^nS_n$ は
$$\begin{aligned}
&\bigg(f-\frac{1}{1-y}\bigg)^2(1-(f-1)+(f-1)^2-(f-1)^3+\dots)\\\\
&=\bigg(f-\frac{1}{1-y}\bigg)^2\frac{1}{1+(f-1)}\\\\
&=\frac{1}{f}\bigg(f-\frac{1}{1-y}\bigg)^2\\\\
&=f+\frac{1}{f}\frac{1}{(1-y)^2}-\frac{2}{1-y}
\end{aligned}$$
の $x^{N}y^{M}$ の係数となる．よって，
$$\frac{g^k}{\sqrt{1-4x}}=\sum_{i=0}^{\infty}\binom{2i+k}{i}x^i$$ 
に気を付ければ以下のように計算できる．
$$ \begin{aligned}
[x^{N}y^{M}]&\bigg(f+\frac{1}{f}\frac{1}{(1-y)^2}-\frac{2}{1-y}\bigg) \\\\
&=[x^{N}y^{M}]f+[x^{N}y^{M}]\frac{1}{f}\frac{1}{(1-y)^2}\\\\
&=[x^{N}y^{M}]\frac{1}{\sqrt{1-4x}}\frac{1}{1-g^4y}+[x^{N}y^{M}]\frac{1-4x}{\sqrt{1-4x}} (1-g^4y)\frac{1}{(1-y)^2}\\\\
&=[x^{N}]\frac{g^{4M}}{\sqrt{1-4x}}+[x^{N}]\frac{1-4x}{\sqrt{1-4x}} (M+1-Mg^4)\\\\
&=[x^{N}]\frac{g^{4M}}{\sqrt{1-4x}}+(M+1)[x^{N}]\frac{1}{\sqrt{1-4x}}-4(M+1)[x^{N-1}]\frac{1}{\sqrt{1-4x}}\\\\
&-M[x^{N}]\frac{g^4}{\sqrt{1-4x}}+4M[x^{N-1}]\frac{g^4}{\sqrt{1-4x}}\\\\
&=\binom{2N+4M}{N}+(M+1)\binom{2N}{N}-4(M+1)\binom{2(N-1)}{N-1}-M\binom{2N+4}{N}+4M\binom{2(N-1)+4}{N-1}\\\\
\end{aligned}
$$
ここで，素数 $p = 8999$ により $N = p+1, ~ M = p-1$ と表せることより，
$$ \binom{2N+4M}{N} \equiv \binom{6p-2}{p+1} \equiv -10 $$
$$ -M\binom{2N+4}{N} \equiv \binom{2p+6}{p+1} \equiv 12 $$
$$ 4M\binom{2(N-1)+4}{N-1} \equiv -4\binom{2p+4}{p} \equiv -8 $$
が $\mathrm{mod} ~ p$ で成立し，残りの項は $\mathrm{mod} ~ p$ で $0$ であるため，解答すべき値は
$$ -10 + 12 - 8 \equiv \mathbf{8993} \pmod{p} $$
である．
公式解説
https://onlinemathcontest.com/contests/omce002/editorial/8694
　当 F 問題では，問題文で与えるべき制約条件に不足が生じている状態で出題されたため，コンテスト中に登録されていた解答が正当とは異なっていました．Unrated となってしまったことを重ねてお詫び申し上げます．

　以下に，原案の問題のアイデアを用いて正しく解ける問題文とその解説を掲載します．面白いアイデアを活かした問題だと思いますので，是非このバージョンにも挑戦していただければと思います．この問題に対する解説はユーザー解説に収録されています．

**問題．** $2$ 以上 $17998$ 以下の整数 $n$ に対し，整数の組 $(a_1,a_2,\ldots,a_{n},b_1,b_2,\ldots,b_{n})$ であって 
$$a_1+a_2+\cdots+a_{n}=9000, \quad a_1 \neq 0$$
$$b_1+b_2+\cdots+b_{n}=8998, \quad a_n\neq0$$
および，任意の $n$ 以下の正の整数 $k$ について
$$-\frac{a_k}{4} \leq b_k \leq 8998, \quad 0 \leq a_k \leq 8999$$
$$0 \leq \sum_{i=1}^{k} b_i \leq 8998, \quad (a_k,b_k)\ne(0,0)$$
を満たすものすべてについての $\displaystyle \prod_{k=1}^{n} {}\_{2a_k+4b_k}\mathrm{C}\_{a_k}$ の総和を $S_n$ とします．\
　$\displaystyle\sum_{n=2}^{17998}(-1)^nS_n$ を素数 $8999$ で割った余りを求めてください．
本来想定されていた出題 - 問題文
https://onlinemathcontest.com/contests/omce002/editorial/8694/497
**解説．** 以下，$p=8999$ とする．座標平面上で
$$(4m+n, n) \quad (0 \leq m \leq p-1, ~ 1 \leq n \leq p)$$ 
と表される $p^2$ 個の点を**落とし穴**と呼ぶこととする．すると $\sum_{n=2}^{17998} (-1)^n S_n$ は，座標平面上を点 $O(0,0)$ から点 $A(5p-3,p+1)$ まで $x$ 方向か $y$ 方向に $1$ だけ進む操作を繰り返して得られる経路のうち，落とし穴を少なくとも $1$ つ通るような経路の総数を包除原理で求めたものである．\
　実際，経路が $n-1$ 個の落とし穴 $T_1, \ldots, T_{n-1}$ を通ると仮定し，始点を $T_0(0,0)$，終点を $T_n(4(p-1)+p+1, p+1)$ とおくと，$1 \leq k \leq n$ について $T_{k-1}$ から $T_k$ への変位は $(a_k+4b_k, a_k)$ とかける．ここで $a_k, b_k$ たちは $0 \leq a_k \leq p, ~ -\dfrac{a_k}{4} \leq b_k \leq p-1$ をみたす整数であり，$a_1 \neq 0, ~ a_n \neq 0$ および
$$ \sum_{k=1}^n (a_k + 4b_k) = 5p-3, \qquad \sum_{k=1}^n a_k = p+1 $$
を満たしている．さらに変位は $0$ ではないので $(a_k, b_k) \neq (0,0)$，また最短経路のみを考えているため $\displaystyle 0 \leq \sum_{i=1}^{k} b_i \leq 8998$ が成り立ち，問題文の条件に合致する．落とし穴を適当な順で $1, 2, \ldots, p^2$ とラベルし，落とし穴 $i$ を通るような経路の集合を $A_i$ とする．落とし穴は高々 $2p-1$ 個までしか踏めないことに注意すると，落とし穴を少なくとも $1$ つ通るような経路の総数 $S$ は包除原理より，
$$ \begin{aligned}
S &= \sum_{1 \leq i_1 \leq p^2} |A_{i_1}| - \sum_{1 \leq i_1 \lt i_2 \leq p^2} |A_{i_1} \cap A_{i_2}| + \cdots + (-1)^{2p-1} \sum_{1 \leq i_1 \lt \cdots \lt i_{2p} \leq p^2} |A_{i_1} \cap \cdots \cap A_{i_{2p-1}}| \\\\
&= S_2 - S_3 + S_4 - \cdots + (-1)^{2p} S_{2p} 
\end{aligned} $$
となるから，示された．

　さて，上記のように解釈できる $S$ を直接計算することを考える．このためには $O$ から $A$ までの ${}\_{6p-2}\mathrm{C}\_{p+1}$ 通りの経路のうち，落とし穴を $1$ つも通らない場合の数を求めればよい．盤面は落とし穴によって分断されているため，直線 $y = 0$ 上のどの点を通るかによって以下のように場合分けできる．
- 点 $(0,1)$ を通るものと点 $(4p-3,0)$ を通るものはそれぞれ $p$ 番目のカタラン数である $\dfrac{{}\_{2p}\mathrm{C}\_{p}}{p+1}$ 通りずつある．
- $k=0,1,\ldots,p-2$ について，点 $(4k+1,0)$ を通るが点 $(4k+5,0)$ を通らない経路は $k$ の値に依らず，$25\cdot2^{p-3}$ 通りである．このことは，点 $(4k+1,0)$ から出発したときの最短経路の総数を点 $(4k+1,0)$ に近い方から順々に計算していくことで得ることができる．

　以上より，
$$ S={}\_{6p-2}\mathrm{C}\_{p+1} - 2 \cdot \dfrac{{}\_{2p}\mathrm{C}\_{p}}{p+1} - (p-1) \cdot 25 \cdot 2^{p-3} $$ 
となる．以下，合同式の法を $p$ とすると，
$${}\_{6p-2}\mathrm{C}\_{p+1}\equiv\dfrac{(6p-2)(6p-3)\cdots(5p+1)5p(5p-1)(5p-2)}{(p+1)p(p-1)\cdots1}\equiv\dfrac{(p-1)!\cdot5\cdot(-2)}{(p-1)!}\equiv-10 $$
$$ \dfrac{{}\_{2p}\mathrm{C}\_{p}}{p+1}\equiv{}\_{2p}\mathrm{C}\_{p}\equiv\dfrac{2p}{p}\cdot\dfrac{2p-1}{p-1}\cdot\dfrac{2p-2}{p-2}\cdot\cdots\cdot\dfrac{p+1}{1} \equiv 2 $$
$$ (p-1) \cdot 25 \cdot 2^{p-3}\equiv\dfrac{-25}{4}\equiv\dfrac{-9024}{4} \equiv -2256 $$
であるから，$S\equiv-10-4+2256\equiv\textbf{2242}$ となる．
本来想定されていた出題 - 解説
https://onlinemathcontest.com/contests/omce002/editorial/8694/498
　$2$ 以上 $17998$ 以下の整数 $n$ に対し，$0$ 以上 $8999$ 以下の整数の組 $(a_1,a_2,\ldots,a_{n},b_1,b_2,\ldots,b_{n})$ であって 
$$a_1+a_2+\cdots+a_{n}=9000, \quad b_1+b_2+\cdots+b_{n}=8998,$$
$$a_1\ne0, \quad a_n\ne0, \quad (a_k,b_k)\ne(0,0) ~~ (k=1,2,\ldots,n)$$
を満たすものすべてについての $\displaystyle \prod_{k=1}^{n} {}\_{2a_k+4b_k}\mathrm{C}\_{a_k}$ の総和を $S_n$ とします．$\displaystyle\sum_{n=2}^{17998}(-1)^nS_n$ を素数 $8999$ で割った余りを求めてください．