版权声明

本题由 搬运，版权归 Codeforces 所有。

题目来源：

• https://codeforces.com/contest/126/problem/D
• https://hydro.ac/p/bzoj-P2660
• https://czoj.com.cn/p/676

题目描述

求将 $n$ 拆分为若干个不同的斐波那契数之和的方案。

输入格式

一行一个正整数 $n\ (1 \le n \le 10^{1000})$。

输出格式

一行一个正整数表示答案。

样例

1

1

2

1

3

2

4

1

5

2

6

2

7

1

8

3

9

2

10

2

11

3

12

1

13

3

14

3

15

2

16

4

17

2

18

3

19

3

20

1