---

Problem 860

---

Gold and Silver Coin Game

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.

Define $F(n)$ to be the number of fair arrangements of $n$ stacks, all of size $2$. Different orderings of the stacks are to be counted separately, so $F(2) = 4$ due to the following four arrangements:

You are also given $F(10) = 63594$.

Find $F(9898)$. Give your answer modulo $989898989$.

---

金银硬币游戏

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

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

定义$F(n)$为所有包含$n$堆、每堆各$2$枚硬币的公平初始局面的数目。堆的顺序不同时视为不同的初始局面，因此$F(2) = 4$，相应的四种初始局面如下所示：

已知$F(10) = 63594$。

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

---