Problem Statement

A function $f(x)$ defined for non-negative integers $x$ satisfies the following conditions.

• $f(0) = 1$.
• $f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor)$ for any positive integer $k$.

Here, $\lfloor A \rfloor$ denotes the value of $A$ rounded down to an integer.

Find $f(N)$.

Constraints

• $N$ is an integer satisfying $0 \le N \le 10^{18}$.

Sample Input 1Copy

2

Sample Output 1Copy

3

We have $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$.

Sample Input 2Copy

0

Sample Output 2Copy

1

Sample Input 3Copy

100

Sample Output 3Copy

55