Problem 895

Gold & Silver Coin Game II

Gary and Sally play a game using gold and silver coins arranged into a number of vertical stacks, alternating turns. On Gary’s turn he chooses a gold coin and removes it from the game along with any other coins sitting on top. Sally does the same on her turn by removing a silver coin. The first player unable to make a move loses.

An arrangement is called fair if the person moving first, whether it be Gary or Sally, will lose the game if both play optimally.

An arrangement is called balanced if the number of gold and silver coins are equal.

Define $G(m)$ to be the number of fair and balanced arrangements consisting of three non-empty stacks, each not exceeding $m$ in size. Different orderings of the stacks are to be counted separately, so $G(2)=6$ due to the following six arrangements:

You are also given $G(5)=348$ and $G(20)=125825982708$.

Find $G(9898)$ giving your answer modulo $989898989$.

金银硬币游戏（二）

盖瑞和萨利在玩一个游戏，游戏开始时有若干堆竖直堆放的金币和银币，两人轮流行动。轮到盖瑞时，他可以任选一枚金币，并将这枚金币和所有堆放在其上方的硬币移出游戏；轮到萨利时则是可以任选一枚银币。首先无法行动的玩家输掉游戏。

如果一个初始局面使得，无论先行玩家是盖瑞还是萨利，他在采取最优策略的情况下都必败，则称之为公平初始局面。

如果一个初始局面的金币和银币的数量相等，则称之为平衡的初始局面。

定义$G(m)$为由三个非空且大小不超过$m$的堆构成的公平且平衡的初始局面的数量。计数时需考虑堆的顺序，因此$G(2)=6$，这六种初始局面如下所示：

已知$G(5)=348$，$G(20)=125825982708$。

求$G(9898)$，并对$989898989$取余作为你的答案。