Counting Odd Binomial Coefficients

Time limit1sMemory limit256 MB

Summary

Count the pairs (m, k) with m below n whose binomial coefficient is odd.

Level: Medium7 of 10
Topics: Number theory, Bit manipulation, Recursion, Combinatorics
Solved: No attempts yet

Problem

For non-negative integers $m$ and $k$ with $k \le m$ , the binomial coefficient is defined as $\binom{m}{k} = \frac{m!}{k!(m-k)!}$ . Let $T_2(n)$ be the number of pairs $(m, k)$ with $0 \le k \le m < n$ such that $\binom{m}{k}$ is odd. The following inequality holds.

$0.812556\,n^{\log_2 3} \le T_2(n) \le n^{\log_2 3}$

Emma does not like an inequality that only brackets the answer, so she wants the exact value of $T_2(n)$ . Help her compute it.

Input

The first line contains one integer $n$ ( $1 \le n \le 10^{11}$ ).

Output

Print the value of $T_2(n)$ on the first line.

Examples3

Example 1
Input
```
4
```
Expected output
```
9
```
Example 2
Input
```
6
```
Expected output
```
15
```
Example 3
Input
```
1
```
Expected output
```
1
```