تابع فیبوناچی تابعی به صورت زیر است:
نمایش عدد $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}$ آمده است.
در تنها سطر خروجی پاسخ سوال را چاپ نمایید.