Problem D: 【2023】数学作业
Memory Limit：128 MB
Time Limit：1.000 S
Judge Style：Text Compare
Creator：
Submit：36
Solved：21
Description
今天小 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 请你帮助他完成他的数学作业。
斐波那契序列指的是这样一个数列：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 请你帮助他完成他的数学作业。
Input
第一行为一个正整数 n。
Output
输出一行一个整数表示答案。
Sample Input Copy
14Sample Output Copy
3HINT
样例输入 2
1110
样例输出 2
21
样例输入 3
1000000000000
样例输出 3
283392
数据范围
本题共有 10 个测试点，每个测试点 10 分。
对于测试点 1-5 ：1<=n<=10^4
对于测试点 6-8 ：1<=n<=10^9
对于测试点 9-10 ：1<=n<=10^12
1110
样例输出 2
21
样例输入 3
1000000000000
样例输出 3
283392
数据范围
本题共有 10 个测试点，每个测试点 10 分。
对于测试点 1-5 ：1<=n<=10^4
对于测试点 6-8 ：1<=n<=10^9
对于测试点 9-10 ：1<=n<=10^12