Description

{{The second stage is related to the famous Fibonacci sequence. Every OIer on Earth knows:

$$F_n = \begin{cases} 1 & (n \le 2) \\ F_{n-1}+F_{n-2} & (n \ge 3) \end{cases}$$

Each term is called a Fibonacci number.

Now given a positive integer $n$, it can be written as a sum of some Fibonacci numbers. If we require that in each representation the Fibonacci numbers are distinct (no repetition), then for a given $n$, how many different ways can it be written?}}

Input Format

{{A single integer $n$.}}

Output Format

{{Output a single integer representing the number of ways.}}

16

4

Hint

{{Hint: 16 = 3 + 13 = 3 + 5 + 8 = 1 + 2 + 13 = 1 + 2 + 5 + 8.

Constraints
For 30% of the testdata, $n \le 256$.
For 100% of the testdata, $n \le 10^{18}$.}}

Translated by ChatGPT 5