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