Un arbore Fibonacci e un arbore binar definit recursiv în felul următor:

• T(0) e arborele vid.
• T(1) e arborele binar cu un singur nod.
• T(k) constă dintr-un nod rădăcină care are nodurile T(k-1) și T(k-2) drept fii.

Pe un astfel de arbore, 2 jucători joacă un joc de preluare. În fiecare rundă, un jucător alege un nod și îl îndepărtează împreună cu subarborele care are rădăcina în acel nod.
Jucătorul care e forțat să îndepărteze rădăcina întregului arbore pierde.

Aici sunt mutările primului jucător în prima runda pentru T(k) unde k ia valori de la 1 la 6.

Fie f(k) numărul de mutări câștigătoare ale primului jucător (adică mutările pentru care al doilea jucător nu are nici o strategie câștigătoare) în prima runda a jocului, atunci când jocul se joacă cu arborele T(k).

De exemplu, f(5) = 1 și f(10) = 17.

Află f(10000). Introdu ultimele 18 cifre ca răspuns.