Dãy số Fibonacci rất quen thuộc đối với sinh viên Tin học được định nghĩa đệ quy như sau:

$$\displaystyle \mathrm{F_n} = \begin{cases} 1 & \text{nếu } n=1 \text{ hoặc } n=2 \\ F_{n-1} + F_{n-2} & \text{nếu } n>2 \end{cases} $$

Xét một tập ~S = \{s_1, s_2, \ldots, s_k\}~ gồm các số Fibonacci phân biệt. Hãy tìm các tập ~S~ mà ~\sum_{i=1}^{k}s_i = n~, với ~n~ cho trước.

Ví dụ với ~n = 13~ ta có các tập sau: ~S = \{13\}, S = \{5, 8\}, S = \{2, 3, 8\}~, không phân biệt thứ tự xuất hiện các số.

Input

Gồm một dòng duy nhất chứa số nguyên dương ~n~ thỏa ~1 \le N \le 10^{18}~.

Output

In ra kết quả cần tìm.

Samples

Sample Input 1

13

Sample Output 1

3

Sample Input 2

16

Sample Output 2

4