题目描述

对于非负整数 $x$，函数 $f(x)$ 满足以下条件。

• $f(0) = 1$。
• 对于任意正整数 $k$，$f(k) = f(\\lfloor \\frac{k}{2}\\rfloor) + f(\\lfloor \\frac{k}{3}\\rfloor)$。

这里，$\\lfloor A \\rfloor$ 表示将 $A$ 向下取整为整数的值。

求 $f(N)$。

约束条件

• $N$ 是满足 $0 \\le N \\le 10^{18}$ 的整数。

输入

输入以标准输入给出，格式如下：

$N$

输出

输出答案。

示例输入 1

2

示例输出 1

3

我们有 $f(2) = f(\\lfloor \\frac{2}{2}\\rfloor) + f(\\lfloor \\frac{2}{3}\\rfloor) = f(1) + f(0) =(f(\\lfloor \\frac{1}{2}\\rfloor) + f(\\lfloor \\frac{1}{3}\\rfloor)) + f(0) =(f(0)+f(0)) + f(0)= 3$。

示例输入 2

0

示例输出 2

1

示例输入 3

100

示例输出 3

55