Sequence
Easy
Execution time limit is 1 second
Runtime memory usage limit is 64 megabytes
Any natural number can be uniquely expressed as a sum of distinct Fibonacci numbers — this concept is the foundation of the Fibonacci numeral system.
Your task is to find the n-th term in the following sequence of numbers:1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100, 10101, …
Input
A natural number N, where N ≤ 10^9.
Output
The N-th term in the sequence.
Examples
Input #1
Answer #1
Submissions 264
Acceptance rate 34%