Problem 605

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)$.



换言之,第$r$轮游戏中,玩家$((r-1) \bmod n) + 1$将会面对玩家$(r \bmod n) + 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$。