题目描述

一个函数 $f(x)$ 对非负整数 $x$ 定义如下：

1. $f(0) = 1$

2. 对于任何正整数 $k$，$f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor)$

其中 $\lfloor A \rfloor$ 表示 $A$ 向下取整的值。给定 $N$，求 $f(N)$。

输入格式

输入为一行，包含一个整数 $N$。

输出格式

输出 $f(N)$ 的值。

样例

2

3

0

1

100

55

样例1解释

我们有 $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 \le N \le 10^{18}$

来源

• AtCoder ABC275D