题目描述

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

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

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

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

输入格式

• 单个整数表示 $N$

输入输出样例 #1

输入 #1

2

输出 #1

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