Update

• [2026.5.3] 使用官方数据代替了前 4 个数据点。

题目描述

某个古老的王国，流通着一种古老的货币。

一天，国王做了一个梦，一觉醒来觉得原来的货币太无聊了，决定采用一种有趣的货币代替原有货币，并给它取了一个名字“牛币”。

于是，他找来了几位大臣，把“牛币”的想法告诉他们。

牛币的面值遵循特殊的序列：$1, 2, 3, 5, 8, 13, 21, 34, \dots$

从第3种面值开始，每种面值都是前两种面值之和，比如$8=3+5$，$34=13+21$。

国王还没想好最大的面值是多少，所以暂时认为面值可以无限大。

假如一个物品的价值是 $x$，它的价值可以恰好用若干枚牛币表示（每个面值最多用 $1$ 枚）。例如，价值 $14$ 的物品，可以有这几种兑换方式：

$14=1+13$（面值 $1$ 和 $13$ 的牛币各 $1$ 枚）

$14=1+5+8$（面值 $1$、$5$ 和 $8$ 的牛币各 $1$ 枚）

$14=1+2+3+8$（面值 $1$、$2$、$3$ 和 $8$ 的牛币各 $1$ 枚）

你是财政大臣，国王交给你一个任务：对于给定的物品价值 $x$，计算出有多少种不同的兑换方案。

输入格式

第一行为一个正整数 $x$，表示物品的价值。

输出格式

一个整数，表示答案。

输入输出样例

14

3

数据范围与提示

$1 \le x\le 10^{12}$