Xét một hàm \(f(x)\) được định nghĩa như sau:

• \(f\) chỉ nhận các tham số nguyên không âm.
• \(f(0)=1\).
• \(f(k)=f\left(\left\lfloor \dfrac{k}{2} \right\rfloor\right)+f\left(\left\lfloor \dfrac{k}{3} \right\rfloor\right)\) với mọi số nguyên dương \(k\).

Trong đó, \(\lfloor A\rfloor\) biểu thị giá trị phần nguyên của một số thực \(A\).

Cho một số nguyên không âm \(N\), hãy tính giá trị \(f(N)\).

Input

• Một dòng duy nhất chứa số nguyên không âm \(N\) \(\left(0\le N\le 10^{18}\right)\).

Output

• In ra giá trị \(f(N)\).

Ví dụ

Sample input 01

2

Sample output 01

3

Giải thích

\(f(2)=f\left(\left\lfloor \dfrac{2}{2} \right\rfloor\right)+\left(\left\lfloor \dfrac{2}{3} \right\rfloor\right)=f(1)+f(0)=f\left(\left\lfloor \dfrac{1}{2} \right\rfloor\right) + f\left(\left\lfloor \dfrac{1}{3} \right\rfloor\right) + f(0) = f(0)+f(0)+f(0)=1+1+1=3\)

Sample input 02

0

Sample output 02

1

Sample input 02

29

Sample output 02

21