P17189 [ICPC 2017 Hong Kong R] Count the Even Integers

Yang Hui’s Triangle is defined as follows. In the first layer, there are two numbers $A_{1,1}$ and $A_{1,2}$ satisfying $A_{1,1} = A_{1,2} = 1$. Then for each $i > 1$, the $i$-th layer contains $i+1$ numbers satisfying $A_{i,1} = A_{i,i+1} = 1$ and $A_{i,j} = A_{i-1,j-1} + A_{i-1,j}$ for $1 < j \le i$. $$ \begin{matrix} 1 & 1 \\ 1 & 2 & 1 \\ 1 & 3 & 3 & 1 \\ 1 & 4 & 6 & 4 & 1 \\ 1 & 5 & 10 & 10 & 5 & 1 \\ 1 & 6 & 15 & 20 & 15 & 6 & 1 \\ 1 & 7 & 21 & 35 & 35 & 21 & 7 & 1 \\ 1 & 8 & 28 & 56 & 70 & 56 & 28 & 8 & 1 \end{matrix} $$ Now, given an integer $N$, you are asked to count the number of even integers in the first $N$ layers.

The input file contains multiple cases, please handle it to the end of file. For each case, there is only one line containing an integer $N$ ($0 < N \le 10^{50}$).

For each case, output the number of the even integers in the first $N$ layers of Yang Hui’s Triangle.