Гарри и Салли играют в игру с серебряными и золотыми монетами, разложенными в несколько вертикальных стопок. Они ходят по очереди. Гарри в свой ход выбирает золотую монету и убирает ее из игры вместе со всеми на ней лежащими монетами. Салли в свой ход аналогичным образом убирает серебряную монету со всеми на ней лежащими. Первый игрок, который больше не может сделать ход, проигрывает.

Расположение монет называется честным, если ходящий первым игрок, будь то Гарри или Салли, проигрывает игру, если оба играют оптимальным образом.

Определим $F(n)$ как количество честных расположений $n$ стопок высотой $2$ каждая. Различные распределения монет в стопках считаются различными расположениями, поэтому $F(2) = 4$ ввиду следующих возможных расположений:

Также известно, что $F(10) = 63594$.

Найдите $F(9898)$. В качестве ответа приведите остаток от деления полученного числа на $989898989$