Sequence#8702

Sequence

1 second

64 megabytes

Easy

Any natural number can be uniquely expressed as a sum of distinct Fibonacci numbers—this is the foundation of the Fibonacci numeral system.

1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100, 10101, \dots

1,\, 10,\, 100,\, 101,\, 1000,\, 1001,\, 1010,\, 10000,\, 10001,\, 10010,\, 10100,\, 10101,\, \ldots

Find the $N$ -th term in the following sequence of numbers:

Input

A natural number $N$ ( $1 \leq N \leq 1 0^{9}$ 1 \le N \le 10^9).

Output the $N$ -th term in the sequence.

Example 1

Loading

1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100, 10101, \dots

1 \leq N \leq 1 0^{9}