Fibonacci number system#4758

Fibonacci number system

1 second

128 megabytes

Very easy

F_{1} = 1, F_{2} = 1, F_{n} = F_{n - 1} + F_{n - 2} for n > 2.

F_1 = 1,\quad F_2 = 1,\quad F_n = F_{n-1} + F_{n-2} \text{ for } n > 2.

Consider the Fibonacci sequence:

Any positive integer can be represented as the sum of several members of the Fibonacci sequence. Such a representation may be ambiguous, but if we impose the additional condition that no two neighboring members of the Fibonacci sequence appear in the representation, then the representation becomes unique.

A = a_{k} F_{k} + \dots + a_{2} F_{2}

A = a_k F_k + \dots + a_2 F_2

We say that an integer $A$ can be represented in the Fibonacci number system in the form $a_{k} a_{k - 1} \dots a_{2}$ a_k a_{k-1} \ldots a_2, where $a_{i}$ a_i equals $0$ or $1$ , if

Here is how small numbers are written in the Fibonacci number system:

Input

One integer $n$ ( $0 \leq n \leq 2 \times 1 0^{9}$ 0 \leq n \leq 2 \times 10^9).

Output

Print the representation of the number $n$ in the Fibonacci number system without leading zeros.

Examples

Example 1

Loading

Example 2

Loading

F_{1} = 1, F_{2} = 1, F_{n} = F_{n - 1} + F_{n - 2} for n > 2.

A = a_{k} F_{k} + \dots + a_{2} F_{2}

a_{k} a_{k - 1} \dots a_{2}

a_{i}

0 \leq n \leq 2 \times 1 0^{9}