[BJOI2012] 最多的方案

题目描述

第二关和很出名的斐波那契数列有关,地球上的 OIer 都知道: $$F_n = \begin{cases} 1 & (n \le 2) \\ F_{n-1}+F_{n-2} & (n \ge 3) \end{cases}$$ 每一项都可以称为斐波那契数。 现在给一个正整数 $n$,它可以写成一些斐波那契数的和的形式。如果我们要求不同的方案中不能有相同的斐波那契数,那么对一个 $n$ 最多可以写出多少种方案呢?

输入输出格式

输入格式


只有一个整数 $n$。

输出格式


一个整数表示方案数。

输入输出样例

输入样例 #1

16

输出样例 #1

4

说明

Hint:16=3+13=3+5+8=1+2+13=1+2+5+8 【数据范围】 对于 $30\%$ 的数据,$n \le 256$; 对于 $100\%$ 的数据,$n \le 10^{18}$。