홀수 이항계수

이항계수 ${m \choose k}$에 익숙할 수도 있다. 이항계수는 ${m \choose k} = \frac{m!}{k!(m-k)!}$로 정의되며, 여기서 $m$과 $k$는 음이 아닌 정수이고 $k \leq m$이다. $0 \le k \le m < n$을 만족하는 홀수 이항계수의 개수를 $T_2(n)$이라 하자. 이 대회에서 배우게 될 가장 유용한 수학적 부등식은 다음과 같다. $0.812556 n^{\log_2 3} \le T_2(n) \le n^{\log_2 3}.$

Emma는 이처럼 부정확한 부등식을 좋아하지 않으며 $T_2(n)$을 정확히 계산하고 싶어 한다. 그녀를 도와줄 수 있는가?

입력은 정수 $n, 1 \leq n \le 10^{11}$ 하나가 있는 한 줄로 주어진다.

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