Hide
Problem J
Odd Binomial Coefficients
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 |
