====== Fibonacci ======

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

  * ‎ $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}$‎ آمده است.‎


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


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

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|21 | 10 |
</WRAP>
  * [[سوال ۲۱|سوال بعد]]
  * [[سوال ۱۹|سوال قبل]]