Hide

Problem H
Odd Binomial Coefficients

/problems/oddbinom/file/statement/en/img-0001.png

You might be familiar with the binomial coefficient ${m \choose k}$ defined as ${m \choose k} = \frac{m!}{k!(m-k)!}$, where $m$ and $k$ are non-negative integers and $k \leq m$. Let $T_2(n)$ 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.812556 n^{\log _2 3} \le T_2(n) \le n^{\log _2 3}. \]

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

Input

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

Output

Output one line with the value of $T_2(n)$.

Sample Input 1 Sample Output 1
4
9
Sample Input 2 Sample Output 2
6
15

Please log in to submit a solution to this problem

Log in