atcoder#ABC275D. [ABC275D] Yet Another Recursive Function

[ABC275D] Yet Another Recursive Function

Score : 400400 points

Problem Statement

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

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

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

Find f(N)f(N).

Constraints

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

Input

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

NN

Output

Print the answer.

2
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$.

0
1
100
55