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).

Input

The input is given from Standard Input in the following format:
N

Output

Print the answer.

Constraints

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

Sample Input 1

2

Sample Output 1

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 2

0

Sample Output 2

1

Sample Input 3

100

Sample Output 3

55

见题面 Input 部分

见题面 Output 部分