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) mod n) + 1$ faces off against player $(r mod 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) mod n) + 1$ 将会面对玩家 $(r mod 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$ 位数字。