Problem 629

Scatterstone Nim

Alice and Bob are playing a modified game of Nim called Scatterstone Nim, with Alice going first, alternating turns with Bob. The game begins with an arbitrary set of stone piles with a total number of stones equal to $n$.

During a player’s turn, he/she must pick a pile having at least $2$ stones and perform a split operation, dividing the pile into an arbitrary set of $p$ non-empty, arbitrarily-sized piles where $2\le p\le k$ for some fixed constant $k$. For example, a pile of size $4$ can be split into ${1,3}$ or ${2,2}$, or ${1,1,2}$ if $k=3$ and in addition ${1,1,1,1}$ if $k=4$.

If no valid move is possible on a given turn, then the other player wins the game.

A winning position is defined as a set of stone piles where a player can ultimately ensure victory no matter what the other player does.

Let $f(n,k)$ be the number of winning positions for Alice on her first turn, given parameters $n$ and $k$. For example, $f(5,2)=3$ with winning positions ${1,1,1,2}, {1,4},{2,3}$. In contrast, $f(5,3)=5$ with winning positions ${1,1,1,2},{1,1,3},{1,4},{2,3},{5}$.

Let $g(n)$ be the sum of $f(n,k)$ over all $2\le k\le n$. For example, $g(7)=66$ and $g(10)=291$.

Find $g(200) \mod(10^9+7)$.

分堆取石子游戏

爱丽丝和鲍勃正在玩一个分堆取石子游戏，爱丽丝先行动，然后轮到鲍勃，如此交替。游戏开始时，将$n$枚石子分成若干堆，每堆中的石子数目任意。

轮到任一玩家行动时，该玩家先选择一堆至少有$2$枚石子，然后将其分成$p$堆，每一堆的石子数任意，但不能为空堆，同时$p$满足$2\le p\le k$，$k$为某个事先约定的常数。例如，一堆共$4$枚石子，如果$k=3$，那么可以分成${1,3}$或${2,2}$或${1,1,2}$；如果$k=4$，那么还可以分成${1,1,1,1}$。

如果轮到某一玩家时没有可行的行动，则对手获胜。

如果玩家在面对特定的石子分堆时，无论对手如何行动，总能保证自己获得最终的胜利，则称之为必胜态。

对于给定的$n$和$k$，记$f(n,k)$为爱丽丝在初次行动时必胜态的数目。例如，$f(5,2)=3$，必胜态包括${1,1,1,2}, {1,4},{2,3}$。此外，$f(5,3)=5$，必胜态包括${1,1,1,2},{1,1,3},{1,4},{2,3},{5}$。

记$g(n)$为遍取$2\le k\le n$时所有$f(n,k)$的和。例如，$g(7)=66$而$g(10)=291$。

求$g(200) \mod (10^9+7)$。