题目描述

金鱼学习 C 语言的时间也不短了，但是看程序写结果的题目对他来说还是太棘手了。今天，金鱼又被一道看程序写结果的题目给难住了，你能帮帮金鱼吗？

难倒小Z的代码：

C/C++版：

long long f(long long x) {
    if (x == 1) return 1;
    return f(x / 2) + f(x / 2 + x % 2);
}

Python版：

def f(x):
    if x == 1:
        return 1
    return f(x // 2) + f(x // 2 + x % 2)

现在给出一个整数 $X$，请输出 $f(X)$ 的值。

输入格式

输入一个正整数 $X(1\le X\le 10^{18})$。

输出格式

输出一个整数，表示 $f(X)$ 的值。

输入样例

2

输出样例

2