Fibonacci System#2425

Fibonacci System

1 second

64 megabytes

Very easy

A positional numeral system based on Fibonacci numbers uses the alphabet ${0, 1}$ , and its basis is the sequence of Fibonacci numbers $1, 2, 3, 5, \dots$ 1, 2, 3, 5, \ldots, that is, the Fibonacci sequence starting from $F (2)$ .

Your task is to convert a given non-negative decimal number $N$ into the Fibonacci numeral system. The result should be a string without leading zeros and without adjacent ones (that is, in the so-called expanded form).

Input

The only line of input contains the number $N$ ( $1 \leq N \leq 2^{62}$ 1 \leq N \leq 2^{62}).

Output

Output a single line containing the answer to the problem.

Examples

Example 1

Loading

1, 2, 3, 5, \dots

1 \leq N \leq 2^{62}