Ambiguity by Fibonacci#3653

Ambiguity by Fibonacci

1 second
64 megabytes
Very easy

In the Fibonacci numeral system, integers are represented using Fibonacci numbers as the basis. This sequence starts with , , , , , , , , , , and so on, beginning from . Each integer is expressed as a binary combination, where the least significant (rightmost) digit corresponds to , the next to , and so forth. A digit of indicates that the corresponding Fibonacci number contributes to the integer's value, while a means it does not. For instance, the representation (101001)_f translates to the number 1 \cdot 1 + 0 \cdot 2 + 0 \cdot 3 + 1 \cdot 5 + 0 \cdot 8 + 1 \cdot 13 = 19. Unlike the standard binary system, the Fibonacci system allows multiple representations for the same number. For example, the number can also be represented as (11111)_f.

Given an integer , your task is to determine how many distinct representations it has in the Fibonacci system.

Input

The input consists of a single integer (-10^7 \le N \le 10^7).

Output

Output a single line containing the number of distinct representations of in the Fibonacci system.

Examples

Example 1

Loading
Loading