Contest Duration: - (local time) (100 minutes) Back to Home
D - Yet Another Recursive Function /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 問題文

• f(0) = 1
• 任意の正整数 k に対し f(k) = f(\lfloor \frac{k}{2}\rfloor) + f(\lfloor \frac{k}{3}\rfloor)

ここで、\lfloor A \rfloorA の小数点以下を切り捨てた値を指します。

このとき、 f(N) を求めてください。

### 制約

• N0 \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


Score : 400 points

### 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}.

### Input

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

N


### 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