Fibonacci Sum Decomposition

Given any positive integer n, it is known that it can be decomposed into several Fibonacci numbers. In this problem, you are asked to compute the number of ways to decompose n into a sum of Fibonacci numbers.

Notes:
1. Use the distinct Fibonacci numbers. Here, we consider the Fibonacci sequence as: 1, 1, 2, 3, 5, 8, ... but treat repeated 1 only once. Thus the set of coins is {1, 2, 3, 5, 8, ...} (all numbers less than or equal to n).
2. The order of summands does not matter (i.e. two decompositions that differ only in the order of the summands are considered the same).

It is guaranteed that every positive integer has at least one decomposition. Your task is to count the total number of decompositions for the given n.

inputFormat

Input format:
The input consists of a single integer n (1 ≤ n ≤ 10^4) representing the number that you have to decompose.

outputFormat

Output format:
Output a single integer that denotes the number of decomposition ways of n into Fibonacci numbers (using each Fibonacci number as a coin, with unlimited supply, and each coin being considered only once even if it appears twice in the classical Fibonacci sequence).

sample

5

6