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</p>

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

예제 입력 1

4

예제 출력 1

9

예제 입력 2

6

예제 출력 2

15