---

Problem 605

---

Pairwise Coin-Tossing Game

Consider an $n$-player game played in consecutive pairs: Round $1$ takes place between players $1$ and $2$, round $2$ takes place between players $2$ and $3$, and so on and so forth, all the way up to round $n$, which takes place between players $n$ and $1$. Then round $n+1$ takes place between players $1$ and $2$ as the entire cycle starts again.

In other words, during round $r$, player $((r-1) \bmod n) + 1$ faces off against player $(r \bmod n) + 1$.

During each round, a fair coin is tossed to decide which of the two players wins that round. If any given player wins both rounds $r$ and $r+1$, then that player wins the entire game.

Let $P_n(k)$ be the probability that player $k$ wins in an $n$-player game, in the form of a reduced fraction. For example, $P_3(1) = 12/49$ and $P_6(2) = 368/1323$.

Let $M_n(k)$ be the product of the reduced numerator and denominator of $P_n(k)$. For example, $M_3(1) = 588$ and $M_6(2) = 486864$.

Find the last $8$ digits of $M_{10^8+7}(10^4+7)$.

---

配对抛掷硬币游戏

考虑如下$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)$为玩家$k$在一个$n$名玩家进行的游戏中获胜的概率。例如$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$位数字。

---