1486 - 数学作业

讨论

统计

通过次数

提交次数

旧版界面

时间限制 : 1 秒

内存限制 : 128 MB

今天小 X 的数学老师带领大家学习了斐波那契序列：

斐波那契序列指的是这样一个数列： ${1,2,3,5,8,13,21,34}$ 。从第 $3$ 个数开始，每个数都是前两个数的和，比如 $8=3+5,34=13+21$ 。数列里的数叫做斐波那契数。

一个数 $n$ 的斐波那契表示是指把 $n$ 写成若干个互不相同的斐波那契数的和。一个数可以有多种不同的斐波那契表示。比如 $14$ 有三种斐波那契表示： $14=1+13,14=1+5+8,14=1+2+3+8$ 。数学老师给小 X 留下了一个数学作业，她告诉小 X 一个正整数 $n$ ，想让小 X 算出 $n$ 有多少种不同的斐波那契表示。

小 X 请你帮助他完成他的数学作业。

输入

第一行为一个正整数 $n$ 。

输出

输出一行一个整数表示答案。

样例

输入

输出

输入

输出

输入

1000000000000

输出

提示

测试点编号	$n$
$1\sim5$	$1\le n\le 10^4$
$6\sim8$	$1\le n\le 10^9$
$9\sim10$	$1\le n\le 10^{12}$

来源

常州市赛