Consider the Fibonacci sequence: F1 = 1, F2 = 1, Fn = Fn-1 + Fn-2 if n > 2.

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

We shall say that A can be represented in the Fibonacci number system in the form akak-1...a2, where ai equals to 0 or 1, if A = akFk + ... + a2F2 and in the notation akak-1...a2 there is no two ones in a row.

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

Number n is given. Find its representation in the Fibonacci number system.

Input

One integer n (0 ≤ n ≤ 2 * 109).

Output

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