OMC221(F)

　$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}$ となる．