Cu mii de ani înainte ca Fibonacci să descopere celebrul șir care îi poartă numele, elfii foloseau deja celebrele proprități ale acestui șir.
    După cum bine știți, elfii erau foarte apropiați de natură, așadar era destul de greu să nu observe că elementele acestui șir, precum și diverse numere derivate din acest șir, apar foarte des în natură.
    Sistemul Fibonacci a fost, la un moment dat, baza matematicii elfilor. Deși au descoperit destul de repede că bazele de numerație tradiționale ușurează calculele, micuții elfi erau nevoiți să învețe și sistemul de numerație pe care noi îl numim Fibonacci.
    Din motive evidente, acest sistem era numit de către elfi sistemul naturii, iar șirul era numit șirul naturii. Numerele scrise în sistemul naturii conțin numai cifre 0 și 1.
    Valoarea zecimală a unui număr scris în sistemul naturii este dată de formula c1 · a1 + c2 · a2 + ... + cn · an, unde c1, c2, ..., cn sunt cifrele numărului scris în sistemul naturii, citite de la dreapta spre stânga, iar a1, a2, ..., an sunt elementele semnificative ale șirului naturii (a1 = 1, a2 = 2, a3 = 3, a4 = 5, a5 = 8, a6 = 13 etc.).
    Să considerăm numărul 1010100000100101 scris în sistemul naturii. Valoarea zecimală a acestui număr este:
1·a1 + 0·a2 + 1·a3 + 0·a4 +
0·a5 + 1·a6 + 0·a7 + 0·a8 +
0·a9 + 0·a10 + 0·a11 + 1·a12 +
0·a13 + 1·a14 + 0·a15 + 1·a16 =
1·1 + 0·2 + 1·3 + 0·5 + 0·8
+ 1·13 + 0·21 + 0·34 + 0·55
+ 0·89 + 0·144 + 1·233 + 0·377
+ 1·610 + 0·987 + 1·1597 =
1 + 3 + 13 + 233 + 610 + 1597 = 2457


Fișierul de intrareINPUT.TXT conține o singură linie pe care se află un singur număr scris în sistemul naturii.

Fișierul de ieșire OUTPUT.TXT trebuie să conțină o singură linie care va conține numărul convertit în sistemul zecimal.

  • numărul scris în sistemul naturii va conține cel mult 20 de cifre și este întotdeauna valid.


  • INPUT.TXT
    1010100000100101

    OUTPUT.TXT
    2457