加里和莎莉用金币和银币交替排列成许多垂直堆叠来玩游戏。轮到加里时，他选择一枚金币，并将其与上面的任何其他硬币一起从游戏中移除。莎莉在轮到她时也做了同样的事情，取出一枚银币。第一个无法采取行动的玩家失败。

如果先行动的人（无论是加里还是莎莉）如果双方都发挥最佳，就会输掉比赛，则这种安排称为公平。

如果金币和银币的数量相等，则这种安排称为平衡。

将 $G(m)$ 定义为由三个非空堆栈组成的公平且平衡的排列数量，每个堆栈的大小不超过 $m$。堆栈的不同顺序要单独计算，因此 $G(2)=6$ 由于以下六种排列：

您还将获得 $G(5)=348$ 和 $G(20)=125825982708$。

找到 $G(9898)$，将你的答案模 $989898989$。