Problem 888

$1249$ Nim

Two players play a game with a number of piles of stones, alternating turns. Each turn a player can choose to remove $1$, $2$, $4$, or $9$ stones from a single pile; or alternatively they can choose to split a pile containing two or more stones into two non-empty piles. The winner is the player who removes the last stone.

A collection of piles is called a losing position if the player to move cannot force a win with optimal play. Define $S(N, m)$ to be the number of distinct losing positions arising from $m$ piles of stones where each pile contains from $1$ to $N$ stones. Two positions are considered equivalent if they consist of the same pile sizes. That is, the order of the piles does not matter.

You are given $S(12,4)=204$ and $S(124,9)=2259208528408$.

Find $S(12491249,1249)$. Give your answer modulo $912491249$.

$1249$取石子游戏

两位玩家正在玩一个游戏：游戏开始时有几堆石子，玩家轮流行动。每一回合，轮到行动的玩家可以从任一堆中移除$1$、$2$、$4$或$9$枚石子，或者将一堆至少两枚石子分成两个非空的堆。移除最后一枚石子的玩家获胜。

如果当前局面使得轮到行动的玩家在最优策略下仍无法获胜，则称之为必败态。定义$S(N, m)$为由$m$堆、每堆包含$1$至$N$枚石子构成的不同必败态的数量。如果两个局面由相同大小的堆构成，则认为它们是相同的，换言之，计算必败态时不计堆的顺序。

已知$S(12,4)=204$，$S(124,9)=2259208528408$。

求$S(12491249,1249)$，并对$912491249$取余作为你的答案。