又一个递归函数

题目描述

定义在非负整数上的函数 $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$

输出格式

输出答案。

样例

2

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$。

0

1

100

55

数据范围

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