تابع فیبوناچی تابعی به صورت زیر است:

• ‎ $f(1) = 1$‎
• ‎ $f(2) = 2$‎
• $f( n \geqslant 3 ) = f(n-1)‎ + ‎f(n-2)$‎

نمایش عدد ‎$x$‎ در مبنای فیبوناچی به صورت زیر است:

‎ ‎$a_n a_{n-1} a_{n-2} \cdots a_1$‎ به‌طوریکه ‎$a_i$‎ یا ‎$0$‎ یا ‎$1$‎ است و ‎$a_n$‎ برابر است با $1$‎. هیچ دو رقم کنارهم برابر با ‎$1$‎ نیستند و ‎$x = \sum_{i=1}^{n} f(i) \times a_i$‎. می‌توان اثبات کرد که این نمایش برای هر عدد یکتاست.

‎ فرض کنید تمام اعداد ‎$1$‎ تا ‎$10^{20}$‎ را در مبنای فیبوناچی نوشته‌ایم و آن‌ها را به ترتیب کنار هم قرار داده‌ایم تا رشته ‎$s$‎ تولید شود. به شما عدد ‎$k$‎ داده شده است، شما باید تعداد ‎$1$های ‎$k$‎ رقم اول رشته ‎$s$‎ را حساب کنید.

‎ برای مثال اگر ‎$k$‎ برابر ‎$21$‎ باشد، ‎$k$‎ رقم اول رشته ‎$s$‎ برابر است با ‎$110100101100010011010$‎ که تعداد یک‌های آن ‎$10$‎ تاست.‎

در تنها سطر ورودی عدد ‎$1 \leqslant k \leqslant 10^{15}$‎ آمده است.‎

در تنها سطر خروجی پاسخ سوال را چاپ نمایید. ‎

• محدودیت زمان: ۲ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

• سوال بعد
• سوال قبل