SPOJ in Armenian

                «...իսկ որ մտնում է անտառը, թվում է, թե ամեն մի ծառի տակից, ամեն մի թփի միջից, ամեն մի քարի ետևից՝ որտեղ որ է գազան է հարձակվելու կամ ավազակ, սարսափած սկսում է գոռգոռալ, ոնց գոռգոռալ՝ ականջդ ոչ լսի։»

Քաջ Նազարը անտառում չվախենալու համար սկսում է բարձրաձայն հաշվել։ Չիմանալով տասական և երկուական համակարգերի մասին, Նազարը հաշվում է Ֆիբոնաչիի հաշվարկման համակարգում։ Վախի պատճառով նա միշտ չէ, որ կարողանում է թվին մեկ գումարել։ Օգնե՛ք Նազարին մեկ գումարել Ֆիբոնաչիի համակարգով գրված թվին։

Թվերի հաջորդականությունը, որում յուրաքանչյուր թիվ հավասար է նախորդ երկուսի գումարին, կոչվում է Ֆիբոնաչիի հաջորդականություն։ Հաջորդականությունը սկսվում է 0 և 1 թվերով։ Այսինքն եթե f_i-ն հաջորդականության i-րդ էլեմենտն է, ապա

f₀ = 0,   f₁ = 1,   f_i = f_i-1 + f_i-2

Հաջորդականության առաջին տասը թվերն են. 0, 1, 1, 2, 3, 5, 8, 13, 21, 34։

 Ֆիբոնաչիի համակարգում բոլոր թվերը բաղկացած են 1 և 0 թվանշաններից։ Ֆիբոնաչիի ներկայացմամբ  N_f=a_ka_k-1...a₁a₀ գրառումը ներկայացնում է a_kf_k+a_k-1f_k-1+...+a₁f₁+a₀f₀ թիվը։ Օրինակ՝ եթե N_f=110101, ապա a_kf_k+a_k-1f_k-1+...+a₁f₁+a₀f₀ =1×5+1×3+0×2+1×1+0×1+1×0=9:։ Նկատենք, որ թվի ներկայացումը Ֆիբոնաչիի համակարգում միակը չէ։

Մուտք

Մուտքի առաջին տողում տրված է մեկ ոչ բացասական N թիվ՝ Ֆիբոնաչիի հաշվարկման համակարգում։ Թվի թվանշանների քանակը չի գերազանցում 1000-ը։

Ելք

Ելքային ֆայլի միակ տողում արտածե՛ք (N+1) թիվը Ֆիբոնաչիի հաշվարկման համակարգում ներկայացումներից որևէ մեկում։ Ձեր պատասխանի երկարությունը չպետք է գերազանցի 2000-ը։

Օրինակ

Մուքը.
110111

Ելքը.
1010001