题目描述

定义函数 $f(x)$ 如下：

• 如果 $x=0$，则 $f(x) = 1$
• 如果 $x>0$，则 $f(x) = f( \lfloor x/2 \rfloor) + f( \lfloor x/3 \rfloor)$

其中 $\lfloor \alpha \rfloor$ 表示令 $\alpha$ 向下取整。

给定 $N$，请计算并输出 $f(N)$

输入格式

• 单个整数表示 $N$

输出格式

2

3

数据范围

• $30\%$ 的数据，$1\leq N\leq 100$
• $60\%$ 的数据，$1\leq N\leq 1,000,000$
• $100\%$ 的数据，$1\leq N\leq 10 ^ {18}$

来源

改编自 ABC275D Yet Another Recursive Function