　$P$ の移動に以下のように名前をつける．
- 操作 $X$ : 点 $P$ を $x$ 方向に $1$ だけ移動させる
- 操作 $Y$ : 点 $P$ を $y$ 方向に $1$ だけ移動させる
- 操作 $Z$ : 点 $P$ を $z$ 方向に $1$ だけ移動させる

　$P$ の移動方法に対して $X,Y,Z$ からなる文字列を対応させることを考える．たとえば，操作 $X$ $\rightarrow$ 操作 $Y$ $\rightarrow$ 操作 $Z$ $\rightarrow$ $\cdots$に対しては，$XYZ\cdots$ と対応させる．いま，$X,Y$ からなる文字列に対し，$X,Y$ をそれぞれ一個ずつ選んで，$Z$ に置き換えることを操作 $Q$ と呼ぶことにする．以下の補題が成り立つ．

---
**補題．**
$n$ 個の $X$ と $m$ 個の $Y$ を並び替えてできるすべての文字列について，操作 $Q$ を行いうるすべての場所に $1$ 度ずつ行ったとき，$n-1$ 個の $X$ と $m-1$ 個の $Y$ ，$2$ 個の $Z$ を並び替えてできる文字列すべてがそれぞれ $2$ 回ずつ登場する．

**証明．**
$n-1$ 個の $X$ と $m-1$ 個の $Y$ ，$2$ 個の $Z$ を並び替えてできる文字列 $T$ に対し，$T$ の $X,Y$ がある位置にはそれぞれ $X,Y$ が位置し，$2$ つの $Z$ の位置には，最初から順に $X,Y$ または $Y,X$ が位置するような $2$ つの文字列が対応するから，補題が従う．

---

　ここで求めるスコアの総和は操作方法に対応させた文字列すべてについて，それに含まれる $100$ 個の $Z$ で区切ってできる $101$ 個の $X,Y$ からなる部分文字列に対し，操作 $Q$ を行う方法の総数である．上の事実より，このとき $400-101$ 個の$X$ と，$400-101$ 個の $Y$ ，$100+101+101$ 個の $Z$ を並び替えてできる文字列すべてが $2^{101}$ 回ずつ登場する (操作 $Q$ からの復元の際，$3k$ 文字目の $Z$ は $X, Y$ に変更されないことに注意)．よって，$$M=\dfrac{900!}{299!299!302!}\times2^{101}$$ であり，これが $2,3$ で割り切れる最大の回数はそれぞれ $112,6$ である．よって，$\gcd(M,6^M)=2^{112}3^6$ であり，解答すべき値は $(112+1)(6+1)=\mathbf{791}$ となる．
公式解説
https://onlinemathcontest.com/contests/omc221/editorial/10100
　$k=0,1,\dots,100$ について 平面 $z=k$ 内で, $x,y$ 方向に $1$ 進む回数をそれぞれ $x_k,y_k$ とおくと, 
スコアは $\prod_{k=0}^{100}x_ky_k$ となり, そのような操作方法は $\prod_{k=0}^{100}\binom{x_k+y_k}{x_k}$ 通りとなる.
したがって, 
$$
\begin{aligned}
x_0+x_1+\dots+x_{100}=400,\\\\
y_0+y_1+\dots+y_{100}=400
\end{aligned}
$$
を満たす非負整数の組 $(x_0,x_1,\dots,x_{100},y_0,y_1,\dots,y_{100})$ すべてについて, 
$$\Bigg(\prod_{k=0}^{100}x_ky_k\Bigg)\Bigg(\prod_{k=0}^{100}\binom{x_k+y_k}{x_k}\Bigg)=\Bigg(\prod_{k=0}^{100}x_ky_k\binom{x_k+y_k}{x_k}\Bigg)$$
の総和を求めれば良い.\
　$x,y$ の $2$ 変数冪級数について以下が成立する. 
$$f(x,y)=\dfrac{1}{1-(x+y)}=\sum_{k=0}^{\infty}(x+y)^k=\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}\binom{i+j}{i}x^iy^j$$
これを用いて, $g(x,y)=\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}ij\binom{i+j}{i}x^iy^j$ は以下のように表示できる.
$$
\begin{aligned}g(x,y)&=\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}ij\binom{i+j}{i}x^iy^j\\\\
&=\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}xy\frac{\partial}{\partial y}\frac{\partial}{\partial x}\Bigg(\binom{i+j}{i}x^iy^j\Bigg)\\\\
&=xy\frac{\partial}{\partial y}\frac{\partial}{\partial x}\Bigg(\sum_{i=0}^{\infty}\sum_{j=0}^{\infty}\Bigg(\binom{i+j}{i}x^iy^j\Bigg)\Bigg)\\\\
&=xy\frac{\partial}{\partial y}\frac{\partial}{\partial x}\Bigg(\frac{1}{1-x-y}\Bigg)\\\\
&=\frac{2xy}{(1-x-y)^3}
\end{aligned}$$
　$M$ は $(g(x,y))^{101}$ の $x^{400}y^{400}$ の係数であり, 以下のように計算できる.
$$
\begin{aligned}
\[x^{400}y^{400}\](g(x,y))^{101}&=\[x^{400}y^{400}\]\frac{(2xy)^{101}}{(1-x-y)^{303}}\\\\
&=2^{101}\[x^{400-101}y^{400-101}\]\frac{1}{(1-(x+y))^{303}}\\\\
&=2^{101}\[x^{299}y^{299}\]\Bigg(\sum_{k=0}^{\infty}\binom{k+302}{302}(x+y)^k\Bigg)\\\\
&=2^{101}\[x^{299}y^{299}\]\Bigg(\binom{(299+299)+302}{302}(x+y)^{299+299}\Bigg)\\\\
&=2^{101}\times\binom{900}{302}\binom{598}{299}\\\\
&=2^{101}\times\frac{900!}{302!299!299!}\\\\
\end{aligned}
$$
となる.
別解
https://onlinemathcontest.com/contests/omc221/editorial/10100/521
　平面 $z = k$ 上で $x$ 軸方向に $x_k$, $y$ 軸方向に $y_k$ だけ移動したとすると，$\displaystyle\sum_{k=0}^{100} x_k = 400, \sum_{k=0}^{100} y_k = 400$ および $S_k =  x_k y_k$ が成立し，$x_k, y_k \gt 0$ としてよい．$\lbrace x_k \rbrace_{k = 0}^{100}$ と $\lbrace y_k \rbrace_{k = 0}^{100}$ の組それぞれに対応する移動方法は $\displaystyle\prod_{k=0}^{100} \dfrac{(x_k + y_k)!}{x_k! y_k!}$ 通り存在するから，スコアへの寄与は
$$\prod_{k=0}^{100} \dfrac{(x_k + y_k)!}{x_k! y_k!} \prod_{k=0}^{100} S_k = 2^{101} \times \prod_{k=0}^{100} \dfrac{(x_k + y_k)!}{(x_k - 1)! (y_k - 1)! 2!}$$
となる．上式の右辺の総積部分は，原点 $(0, 0, 0)$ から点 $(299, 299, 302)$ への移動であって，各 $m = 1, 2, \ldots, 100$ について平面 $z = 3m - 1$ から平面 $z = 3m$ へ移動するときの $x, y$ 座標が $\displaystyle\sum_{k = 0}^{m - 1} (x_k - 1), \displaystyle\sum_{k = 0}^{m - 1} (y_k - 1)$ となるものの総数に等しいから，$M = 2^{101} \times \dfrac{900!}{299!299!302!}$．
ユーザー解説
https://onlinemathcontest.com/contests/omc221/editorial/10100/523
　座標空間内の点 $P$ がはじめ原点 $(0,0,0)$ にあります．$P$ を $x, y, z$ のいずれかの正方向に $1$ だけ移動させる操作を計 $900$ 回行うことで，点 $(400,400,100)$ に移動させることを考えます．\
　$k=0,1,\dots,100$ に対して，各辺が $x$ 軸または $y$ 軸に平行な長方形であって，$P$ の通った $901$ 個の格子点のうち平面 $z=k$ 内に含まれるもの全てをその内部または周上に含むものの面積の最小値を $S_k$ とします．ただし，$z=k$ 内での $P$ の通った格子点が同一直線上に並ぶ，または $1$ 点のみであるとき，$S_k=0$ とします．\
　ここで，一連の操作の **スコア** を $S_0, S_1, \ldots, S_{100}$ の総積で定めます．操作方法は全部で $\dfrac{900!}{400!400!100!}$ 通りありますが，それら全てに対するスコアの総和を $M$ とします．

　このとき，$M$ を求め，$\gcd(M, 6^M)$ の正の約数の個数を解答してください．
　