Description

OceanCat拿到了一份数学题，题目给出了一个f(x)，当x=1时，f(x)=1,当x>1时，f(x)=f(!(x/2)!)+f(!(x/2+x%2)!)[x为正整数]

其中!(x)!表示对x下取整

如果你学过C++函数的话，你可以很轻松地将f(x)翻译成一个函数，代码如下

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

(或许改好格式交上去就可以AC呢

如果没有学过的话就要靠你自己的算力了。

给定一个正整数 x ，他希望你能输出f(x)的值，你能帮帮他吗？ 的值，你能帮帮他么？

Input Format

输入一行包含一个正整数x(1≤x≤1000000000000000000) (不用数了是18个0)## Output Format

输出f(x)即可

1​

1