파스칼의 삼각형

파스칼의 삼각형은 다음과 같은 모양의 무한한 삼각형이다.

파스칼의 삼각형에서 행은 0부터 번호를 매기고, 각 행의 수도 0부터 번호를 매긴다. 0번째 행은 수 하나만 가지며 그 값은 1이고, 각 행은 이전 행보다 수를 하나 더 가진다. 각 행의 0번째 수와 마지막 수는 1이며, 나머지 수는 각각 이전 행에서 자기 위에 있는 두 수의 합이다.

따라서 $i$번째 행은 $i + 1$개의 수를 가진다. $i$번째 행의 $j$번째 원소를 $a_{i,j}$라고 하면 $a_{i,j} = a_{i - 1,j - 1} + a_{i-1,j}$가 성립한다. 이전 행에서 없는 원소(번호가 $-1$인 원소와 $i$인 원소)를 0으로 두면 이 등식은 양 끝 원소에 대해서도 성립한다.

콜라는 파스칼의 삼각형 $n$번째 행에 홀수가 몇 개 있는지 알고 싶어 한다. 삼각형을 그리기 시작했지만 곧 종이에 다 들어가지 않았다. 그래서 콜라는 컴퓨터로 이 일을 하기로 했다. 콜라를 도와주자.

입력 파일에 수 $n$이 주어진다. ($0 \le n \le 2 \cdot 10^9$)

출력 파일에 파스칼의 삼각형 $n$번째 행에 있는 홀수의 개수를 출력한다.