Problem 806

Nim on Towers of Hanoi

This problem combines the game of Nim with the Towers of Hanoi. For a brief introduction to the rules of these games, please refer to Problem 301 and Problem 497, respectively.

The unique shortest solution to the Towers of Hanoi problem with $n$ disks and $3$ pegs requires $2^{n} - 1$ moves. Number the positions in the solution from index $0$ (starting position, all disks on the first peg) to index $2^{n} - 1$ (final position, all disks on the third peg).

Each of these $2^{n}$ positions can be considered as the starting configuration for a game of Nim, in which two players take turns to select a peg and remove any positive number of disks from it. The winner is the player who removes the last disk.

We define $f (n)$ to be the sum of the indices of those positions for which, when considered as a Nim game, the first player will lose (assuming an optimal strategy from both players).

For $n = 4$ , the indices of losing positions in the shortest solution are $3$ , $6$ , $9$ and $12$ . So we have $f (4) = 30$ .

You are given that $f (10) = 67518$ .

Find $f (10^{5})$ . Give your answer modulo $1 000 000 007$ .

汉诺塔取石子游戏

本题结合了“取石子游戏”和“汉诺塔”这两种游戏，其规则介绍请分别参见第301题和第497题。

对于包含 $n$ 个盘子和 $3$ 根柱子的标准汉诺塔问题，其唯一的最优解法共需 $2^{n} - 1$ 步。将该解法中出现的所有状态分别编号，初始状态（所有盘子都在第一根柱子上）编号为 $0$ ，最终状态（所有盘子都在第三根柱子上）编号为 $2^{n} - 1$ 。

这 $2^{n}$ 种状态中的每一种都可以视为取石子游戏的一个初始布局。由此布局开始，两名玩家轮流选择一根柱子，并从中移走任意数量为正的盘子。移走最后一个盘子的玩家获胜。

考虑所有作为取石子游戏初始布局时先手玩家必败的状态（假设两名玩家均采用最优策略），记 $f (n)$ 为这些状态的编号之和。

对于 $n = 4$ ，所有必败初始状态的编号为 $3$ 、 $6$ 、 $9$ 和 $12$ ，因此 $f (4) = 30$ 。

已知 $f (10) = 67518$ 。

求 $f (10^{5})$ ，并将你的答案对 $1 000 000 007$ 取余。