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

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

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

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