Ambiguity by Fibonacci
In the Fibonacci numeral system, integers are represented using Fibonacci numbers as the basis. This sequence starts with 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, and so on, beginning from F(2). Each integer is expressed as a binary combination, where the least significant (rightmost) digit corresponds to 1, the next to 2, and so forth. A digit of 1 indicates that the corresponding Fibonacci number contributes to the integer's value, while a 0 means it does not. For instance, the representation (101001)_f translates to the number 1·1 + 0·2 + 0·3 + 1·5 + 0·8 + 1·13 = 19. Unlike the standard binary system, the Fibonacci system allows multiple representations for the same number. For example, the number 19 can also be represented as (11111)_f.
Given an integer N, your task is to determine how many distinct representations it has in the Fibonacci system.
Input
The input consists of a single integer N (-10^{7} ≤ N ≤ 10^7).
Output
Output a single line containing the number of distinct representations of N in the Fibonacci system.