Дерево Фибоначчи - это двоичное дерево, рекурсивно задаваемое следующим образом:

• T(0) - пустое дерево.
• T(1) - двоичное дерево с одним узлом.
• T(k) состоит из корневого узла, имеющего T(k-1) и T(k-2) в качестве потомков.

Два игрока играют в игру с таким деревом. Каждый ход игрок выбирает узел и убирает его вместе со всем поддеревом, исходящим из этого узла.
Игрок, вынужденный убрать корневой узел всего дерева, проигрывает.

Ниже показаны выигрышные первые ходы первого игрока при игре с деревом T(k) от k=1 до k=6.

Пусть f(k) будет количеством выигрышных первых ходов для первого игрока (т.е. первых ходов, после которых второй игрок лишен выигрышной стратегии) в игре с деревом T(k).

Например, f(5) = 1 и f(10) = 17.

Найдите f(10000). Приведите последние 18 цифр полученного числа.