　ここではゲームの**状態**を黒板に書かれた整数の多重集合（同じ元がいくつ含まれるかも合わせて考える）とする．まずは黒板に書かれるものは正整数であれば何でも，何個でもよいとして考える．このとき，各状態 $P$ について，そのGrundy数を $g(P)$ と表す．また，正整数 $x$ に対して $g(\\{x\\})$ を単に $g(x)$ と表す．

<details><summary>Grundy数について<\/summary>
　以下の特徴を持つゲームは**不偏ゲーム**と呼ばれる．本問もこれに該当する．

- 二人で交互に操作を行う．
- どちらかが勝ち，どちらかが負ける．
- ありうる状態は有限個であり，どのような操作を行っても，有限回でこれ以上操作できない状態になる．
- 操作は偶然性に左右されない．
- 二人は互いのすべての情報を持っている．
- 二人が行うことのできる操作は，同じ状態に対しては同一である．
- 操作を行えなくなった方が負けである．

不偏ゲームは初期状態から勝敗が確定し，**Grundy数** という概念を用いてその状態を調べることができる．まず関数 $\operatorname{mex}$ を次のように定義する．

- 非負整数の有限多重集合 $S$ について，$S$ の元ではない最小の非負整数を $\operatorname{mex}(S)$ とする．\
特に空集合については $\operatorname{mex}(\emptyset)=0$ である．

各ゲームの状態 $P$ について，そのGrundy数 $g(P)$ は次のようにして定義される．
- $P$ から $1$ 回の操作で遷移できる状態全体の集合を $S$ として $g(P)=\operatorname{mex}(\\{g(Q)\mid Q\in S\\})$ とする．

このとき定義より次が容易にわかる．
- それ以上操作できない状態のGrundy数は $0$．
- Grundy数が $0$ の状態からはGrundy数が $0$ の状態へ遷移できない．
- Grundy数が $0$ でない状態からはGrundy数が $0$ の状態へ遷移できる．

これらを合わせれば，ゲームが状態 $P$ から始まるとき $g(P)=0$ なら後手必勝，そうでないなら先手必勝となることがわかる．
<\/details>

　本問のゲームでは黒板に書かれたどの $2$ つの整数も操作において独立であるから，Grundy数の重要な性質（Sprague–Grundyの定理）を用いれば，次の性質がわかる．

- 状態 $P,Q$ に対して和 $P+Q$ を多重集合の和と定義する．このとき次が成り立つ．
$$g(P+Q)=g(P) \oplus g(Q).$$
ただし非負整数 $x,y$ に対して $x\oplus y$ は $2$ 進数表記での排他的論理和を表す．

**補題**．次が成り立つ．
- $x$ が奇数または $x=2$ のとき $g(x)=0$．
- $x$ が $4$ の倍数のとき $g(x)=1$．
- $x$ が $6$ 以上の $4$ の倍数でない偶数のとき $g(x)=2$．

<details><summary>補題の証明<\/summary>
　$x$ に関する帰納法で示す．$g(1)=0, g(2)=0$ は容易に確かめられる．$x\geq 3$ とし，任意の $y(\lt x)$ に対して補題が成り立つと仮定する．

　(1) $x$ が奇数のとき：$x$ が素数ならば明らかに $g(x)=0$ である．そうでないとき，操作で書き込まれる整数 $y,z(\lt x)$ の偶奇は異なり，また $y,z$ が互いに素でないことから $y,z$   はどちらも $2$ でない．よって $g(y)\neq g(z)$，すなわち $g(y)\oplus g(z)\neq 0$ がわかるため，${x}$ から遷移できる任意の状態に対するGrundy数は $0$ ではない．よって $g(x)=0$ である.

　(2) $x$ が $4$ の倍数のとき：$x=4$ の場合は $y=z=2$ しかあり得ないことから $g(4)=1$ である．$x\ge 8$ のとき，操作で書き込まれる整数 $y,z$ としては次の $4$ つの場合が考えられる．
- どちらも奇数である
- どちらも $4$ の倍数である（$(y,z)=(4,x-4)$ が常に考えられる）
- どちらも $4$ の倍数でない $6$ 以上の偶数である
- 一方が $2$，もう一方が $4$ の倍数でない $6$ 以上の偶数である

このうち上 $3$ つの場合は $g(y)\oplus g(z)=0$，最後の場合は $g(y)\oplus g(z)=2$ であるから $g(x)=1$ が得られる．

　(3) $x$ が $6$ 以上の $4$ の倍数でない偶数のとき：操作で書き込まれる整数 $y,z$ としては次の $3$ つの場合が考えられる．
- どちらも奇数である（$(y,z)=(x\/2,x\/2)$ が常に考えられる）
- 一方が $2$，もう一方が $4$ の倍数である（$(y,z)=(2,x-2)$ が常に考えられる）
- 一方が $4$ の倍数でない $6$ 以上の偶数，もう一方が $4$ の倍数である

$1$ つ目の場合は $g(y)\oplus g(z) = 0$，$2$ つ目の場合は $g(y)\oplus g(z)=1$，$3$ つ目の場合は $g(y)\oplus g(z) = 3$ であるから $g(x)=2$ が得られる．

以上より補題は示された．
<\/details>

本問における最初の状態 $P_0$ は $P_0=\\{s_1,s_2,\dots ,s_{5000}\\}$ より
$$g(P_0)=g(s_1)\oplus g(s_2)\oplus \dots \oplus g(s_{5000})$$
である．あなたが勝つのは $g(P_0)=0$ と同値であり，$2$ 進法表記で各桁ごとに独立に考えることで次の条件を得る.

- $s_1,s_2,\dots ,s_{5000}$ のうち，$4$ の倍数は偶数個 ($2a$ 個とする) である．
- $s_1,s_2,\dots ,s_{5000}$ のうち，$6$ 以上の $4$ の倍数でない偶数は偶数個 ($2b$ 個とする) である．

　$149$ 以下の正整数のうち $4$ の倍数は $37$ 個，$6$ 以上の $4$ の倍数でない偶数は $36$ 個であるから，

$$M=\sum_{a=0}^{2500} \sum_{b=0}^{2500-a} \dfrac{5000!}{(2a)!(2b)!(5000-2a-2b)!}37^{2a}\cdot 36^{2b} \cdot 76^{5000-2a-2b}$$
と表せる．これは $f(s,t)=(36s+37t+76)^{5000}$ において $s,t$ の次数がともに偶数である項の係数の総和であるから，
$$\frac{f(1,1)+f(1,-1)+f(-1,1)+f(-1,-1)}{4} =\frac{149^{5000}+75^{5000}+77^{5000}+3^{5000}}{4}$$
と求められる．この $4$ 倍（$4M$）を $4999$ で割った余りについて，Fermatの小定理より
$$4M\equiv 149^2+75^2+77^2+3^2\equiv 3770 \pmod{4999}$$
であるから，これを $4$ で割る（$=1250$ を掛ける）ことで求める値は $M\equiv {\bf{3442}} \pmod{4999}$ となる．
公式解説
https://onlinemathcontest.com/contests/omc133/editorial/4881
　無数にある白紙のカードを使って，あなたはOMC君と次のゲームを行います．

---

【**ルール**】まず，ゲームマスターが次の一連の操作を $5000$ 回続けて行う．
- $1$ 以上 $149$ 以下の整数のうち一つを任意に選ぶ．\
これが $i$ 回目（$i=1,\ldots,5000$）の操作のとき，選ばれた数を $s_i$ とする．
- 白紙のカードを $1$ 枚とり，$s_i$ を書き込む．

ただし，ゲームマスターはゲームの進行に中立な存在である．\
　その後，あなたとOMC君は交互に次の一連の操作を行う．**OMC君が先攻である**．

- $2$ 以上の整数が書き込まれたカードを $1$ 枚選び，白紙に戻す．\
書き込まれていた数を $x$ とする．
- 次の条件をみたす正整数 $y,z$ を任意に選ぶ．
  - $y,z$ は互いに素**ではなく**，かつ $x=y+z$ をみたす．
- 白紙のカードを $2$ 枚とり，それぞれに $y,z$ を書き込む．

　先に操作を行えなくなった方が負けであり，もう一方が勝ちである．

---

　両者が自身の勝ちのために最適に行動します．このとき，ゲームは有限回の操作で終了し，組 $(s_1,s_2,\dots ,s_{5000})$ ごとにあなたとOMC君のいずれが最終的に勝つかが定まります．$149^{5000}$ 通りある組のうち，あなたが最終的に勝つものは $M$ 通りあります．\
　$M$ を素数 $4999$ で割ったあまりを求めてください.