홀수인 이항계수의 개수

$m$과 $k$가 음이 아닌 정수이고 $k \le m$일 때, 이항계수는 $\binom{m}{k} = \frac{m!}{k!(m-k)!}$로 정의된다. $0 \le k \le m < n$을 만족하는 순서쌍 $(m, k)$ 중에서 $\binom{m}{k}$가 홀수인 것의 개수를 $T_2(n)$이라고 하자. 다음 부등식이 성립한다.

$0.812556\,n^{\log_2 3} \le T_2(n) \le n^{\log_2 3}$

엠마는 이렇게 범위만 알려 주는 부등식이 마음에 들지 않아 $T_2(n)$을 정확히 계산하려고 한다. 엠마를 도와주자.

첫째 줄에 정수 $n$이 주어진다. ($1 \le n \le 10^{11}$)

첫째 줄에 $T_2(n)$의 값을 출력한다.