시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 5 1 1 100.000%

문제

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)\).

예제 입력

4

예제 출력

9

예제 입력 2

6

예제 출력 2

15

힌트