605：ペアごとのコイントスゲーム

n人のプレイヤーが隣り合ったペア同士で行うゲームを考える。1ラウンド目にはプレーヤー1と2が、2ラウンド目にはプレーヤー2と3が、というようにして、nラウンド目にはプレーヤーnと1が勝負を行う。$n+1$ ラウンド目には1と2が行い、その後は同じように繰り返していく。

つまり、$r$ ラウンド目にはプレーヤー $((r-1) \bmod n)+1$ とプレーヤー $(r \bmod n)+1$ が勝負をする。

各ラウンドでは、公平なコインを投げることによってどちらのプレーヤーの勝ちかを決める。あるプレーヤーがラウンド r と r+1 で両方勝ったとき、そのプレーヤーをこのゲーム全体の勝者とする。

$P_n(k)$ を、n人で行うゲームでプレーヤーkが勝者となる確率を既約分数で表したものとする。 例えば、$P_3(1)=12/49,$ $P_6(2) = 368/1323$ である。

$M_n(k)$ を、$P_n(k)$ の分子と分母の積とする。 例えば、$M_3(1) = 588,$ $M_6(2) = 486864$ である。

$M_{10^8+7}(10^4+7)$ の末尾の8桁を求めよ。