　点 $P$ が直線 $x=2000$ より先に直線 $y=2000$ にたどり着く確率は対称性より $\dfrac{1}{2}$ である．このことは，点 $P$ が点 $(1999,2000)$ を通る確率が $\dfrac{1}{2}$ であると言い換えられる．一方で，点 $P$ が点 $(2000,1999)$ に着く確率は $\dfrac{\_{3999}\mathrm{C}\_{1999}}{2^{3999}}$ であるから（動ける範囲が $x\geq 0,y\geq 0$ 全体として考えたのと同じ），点 $P$ が点 $(2000,2000)$ を通る確率は以下で与えられる．
$$\dfrac{2^{3999}+{}\_{3999}\mathrm{C}\_{1999}}{2^{4000}}$$
　 ${}\_{3999}\mathrm{C}\_{1999}$ の $2$ で割り切れる回数は $5$ 回である（ここで，$n!$ が $2$ で割り切れる回数は，$n$ を $2$ 進法表示したときの $1$ の個数を $k$ として $n-k$ であることを用いることもできる）．よって，求める値は
$$({}\_{3999}\mathrm{C}\_{1999}+2^{3999}+2^{4000})\div32$$
を $4001$ で割った余りである．以下，合同式の法は $4001$ とする．
$${}\_{3999}\mathrm{C}\_{1999}\equiv\dfrac{3999\times\cdots\times2001}{1999!}\equiv\dfrac{(-2)\times\cdots\times(-2000)}{1999!}\equiv-2000$$
であることと，Fermatの小定理より $2^{4000}\equiv1,~2^{3999}\equiv2^{-1}\equiv2001$ であることより，
$$({}\_{3999}\mathrm{C}\_{1999}+2^{3999}+2^{4000})\times{32}^{-1}\equiv(-2000+1+2001)\times{32}^{-1}\equiv{16}^{-1}\equiv\textbf{3751}.$$
公式解説
https://onlinemathcontest.com/contests/omc142/editorial/2730
　端の制約をなくして $4000$ 回 $P$ を移動させることを考える．このとき求める確率は $(0, 4000), (1, 3999), \ldots, (2000, 2000)$ のどれかにいる確率であるから
$$ \sum_{k=0}^{2000}\frac{{}\_{4000}\mathrm C\_r}{2^{4000}} = \frac{2^{4000} + {}\_{4000}\mathrm C\_{2000}}{2^{4001}}\mathrel{\left(=\frac{2^{3999} + {}\_{3999}\mathrm C\_{1999}}{2^{4000}}\right)}\mathclose{}. $$
あとは本解説と同様（ただカッコの前の形で ${}\_{p-1}\mathrm C\_r \equiv (-1)^r \pmod p$ を使うとラク）．
対称性を式で処理
https://onlinemathcontest.com/contests/omc142/editorial/2730/191
　座標平面上に点 $P$ があり，はじめは原点 $(0,0)$ にあります．\
　以下の規則に従って $P$ を $4001$ 回動かすと，最終的に $P$ は点 $(2001,2000)$ に達します．このとき，$P$ が途中で点 $(2000,2000)$ を通る確率を求めてください．

- $P$ が $x=2001$ 上にあるとき，$P$ を $y$ 軸の正の方向に $1$ だけ動かす．
- $P$ が $y=2000$ 上にあるとき，$P$ を $x$ 軸の正の方向に $1$ だけ動かす．
- $P$ がそれ以外の領域にあるとき，$P$ を $x$ 軸の正の方向に $1$ だけ動かす操作と $y$ 軸の正の方向に $1$ だけ動かす操作のうち，ちょうど一方を等確率に行う．

ただし，求める値は互いに素な正の整数 $a,b$ を用いて $\dfrac{a}{b}$ と表されるので，$a+b$ を素数 $4001$ で割った余りを求めてください．