　一般に $10000$ を $N$ とおく．各 $r = 0, \ldots, N$ に対し，$M \ge r$ となる $A,B$ の並べ替えの総数は，カタラン数と同様の鏡像法によって ${}\_{2N}\mathrm C\_{N-r}$ と分かる．よって求める総和 $S$ は
$$ S = \sum\_{r=0}^{N-1} r^2 \left( {}\_{2N}\mathrm C\_{N-r} - {}\_{2N}\mathrm C\_{N-(r+1)} \right) + N^2 {}\_{2N}\mathrm C\_0 = \sum\_{r=0}^{N-1} \mathopen{}\left( 2N - 1 - 2r \right) {}\_{2N}\mathrm C\_r. $$
ここで
$$ \sum\_{r=0}^{N-1} {}\_{2N}\mathrm C\_r = \frac12 \left( \sum\_{r=0}^{2N} {}\_{2N}\mathrm C\_r - {}\_{2N}\mathrm C\_N \right) = 2^{2N-1} - \frac{{}\_{2N}\mathrm C\_N}2, $$
また同様にして
$$ \sum\_{r=0}^{N-1} r\\,{}\_{2N}\mathrm C\_r = 2N \sum\_{r=1}^{N-1} {}\_{2N-1}\mathrm C\_{r-1}  = N \left(2^{2N-1} - {}\_{2N}\mathrm C\_N\right)$$
が成立するから，これらを代入して
$$ S = \frac{2N + 1}2 \times {}\_{2N}\mathrm C\_N - 2^{2N-1} = 20001 \times \dfrac{{}\_{20000}\mathrm C\_{10000}}2 - 2^{19999}. $$
　${}\_{20000}\mathrm C\_{10000}$ が $2^5$ の倍数であることから $\dfrac{{}\_{20000}\mathrm C\_{10000}}2 \equiv 8320\pmod{10^4}$．また Euler の定理より
$$2^{19999}=2^{-1}\times 2^{40\times\varphi (5^4)} \equiv 2^{-1}\equiv \dfrac{1+15\times 5^4}{2}\equiv 4688 \pmod{5^4}.$$
$4688$ は $2^4$ の倍数であるから, $2^{19999}$ を $10^4$ で割った余りも $4688$ である. 以上より,
$$S \equiv 20001 \times 8320 - 4688 \equiv \textbf{3632} \pmod{10^4}$$
公式解説
https://onlinemathcontest.com/contests/omc081/editorial/2500
　黒板に $0$ が一つだけ書かれています．ここへ以下の操作 $A,B$ をそれぞれ $10000$ 回ずつ適当な順序で施します：

- 操作 $A$：黒板に書かれている数が $n$ のとき，これを $n+1$ に書き換える．
- 操作 $B$：黒板に書かれている数が $n$ のとき，これを $n-1$ に書き換える．

この過程で黒板に書かれたすべての数について，その最大値を $M$ とします．\
　操作 $A,B$ を行う順序は全部で ${}\_{20000}\mathrm C\_{10000}$ 通りありますが，すべてについて $M^2$ の総和を求め，それを $10000$ で割った余りを求めてください．ただし，${}\_{20000}\mathrm C\_{10000}$ を $10000$ で割った余りは $6640$ です．