Hide

# 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 |

CPU Time limit
1 second

Memory limit
1024 MB

Difficulty
3.5medium

Statistics
Show

Downloads

Author

Source
KTH Challenge 2015