Problem 325

Stone Game II

A game is played with two piles of stones and two players.
On each player’s turn, the player may remove a number of stones from the larger pile.
The number of removed must be a positive multiple of the number of stones in the smaller pile.

E.g., let the ordered pair $(6, 14)$ describe a configuration with $6$ stones in the smaller pile and $14$ stones in the larger pile, then the first player can remove $6$ or $12$ stones from the larger pile.

The player taking all the stones from a pile wins the game.

A winning configuration is one where the first player can force a win. For example, $(1, 5)$ , $(2, 6)$ and $(3, 12)$ are winning configurations because the first player can immediately remove all stones in the second pile.

A losing configuration is one where the second player can force a win, no matter what the first player does. For example, $(2, 3)$ and $(3, 4)$ are losing configurations: any legal move leaves a winning configuration for the second player.

Define $S (N)$ as the sum of $(x_{i} + y_{i})$ for all losing configurations $(x_{i}, y_{i})$ , $0 < x_{i} < y_{i} \leq N$ .

We can verify that $S (10) = 211$ and $S (10^{4}) = 230312207313$ .

Find $S (10^{16}) mod 7^{10}$ .

取石子游戏（二）

两名玩家正在用两堆石子玩游戏。
每一轮，玩家可以从较大的堆中取走一定数量的石子。
移走石子的数量必须是较小的堆中石子数量的正整数倍。

例如，用有序对 $(6, 14)$ 表示游戏中较小的堆有 $6$ 枚石子，较大的堆有 $14$ 枚石子，先手玩家可以从较大的堆中取走 $6$ 枚或 $12$ 枚石子。

从某一堆中取走所有石头的玩家赢得游戏。

所谓必胜态指先手玩家必胜的状态。例如 $(1, 5)$ 、 $(2, 6)$ 和 $(3, 12)$ 都是必胜态，因为先手玩家可以立即取走第二个堆中的所有石子。

所谓必败态指无论先手玩家如何操作，后手玩家都必胜的状态。例如， $(2, 3)$ 和 $(3, 4)$ 都是必败态：先手玩家的任意合法操作都会给后手玩家留下必胜态。

对于所有 $0 < x_{i} < y_{i} \leq N$ 的必败态 $(x_{i}, y_{i})$ ，记 $S (N)$ 为 $(x_{i} + y_{i})$ 的和。

可以验证 $S (10) = 211$ ， $S (10^{4}) = 230312207313$ 。

求 $S (10^{16}) mod 7^{10}$ 。

译注：“取石子游戏（一）”参见第260题。