11219번 - Odd Binomial Coefficients 다국어

You might be familiar with the binomial coefficient \(\binom{m}{k}\) defined as \(\binom{m}{k} = \frac{m!}{k!(m-k)!}\), where \(m\) and \(k\) are non-negative integers and \(k \le m\). Let \(T_2\left(n\right)\) be the number of odd binomial coefficients such that \(0 \le k \le m < n \). The most useful mathematical inequality you will learn during this competition is

\[0.812556n^{\log_2{3}} \le T_2\left(n\right) \le n^{\log_2{3}}\]

Emma doesn’t like such imprecise inequalities and would like to calculate \(T_2\left(n\right)\) exactly. Can you help her?

The input contains one line with one integer \(n\), \(1 \le n \le 10^{11}\).

Output one line with the value of \(T_2\left(n\right)\).