Fibonacci Representation Count

Given a positive integer n, you are asked to represent it as the sum of several distinct Fibonacci numbers. The Fibonacci sequence used in this problem is defined as follows: $$\{1, 2, 3, 5, 8, 13, 21, \dots\}$$. Starting from the 3rd term, each number is the sum of the previous two, e.g., $$8=3+5$$ and $$34=13+21$$. For instance, the number 14 has three different representations:

$$14=1+13, \quad 14=1+5+8, \quad 14=1+2+3+8$$

Your task is to compute the number of different Fibonacci representations of the given integer n.

inputFormat

The input consists of a single positive integer n.

outputFormat

Output a single integer: the number of different ways to represent n as the sum of several distinct Fibonacci numbers from the defined sequence.

sample

1

1