Counting Odd Binomial Coefficients

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.

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

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