题目描述

Donald loves nature. Being a programmer, Donald writes programs to simulate the growth of trees or to build realistic 3D landscapes. For this purpose, Donald needs a good pseudo-random number generator. He devises the following method to produce an infinite sequence of 40-bit unsigned integers (the lines in green are comments).

$$\begin{aligned} M &:= 1 \ll 40 & // &= 2^{40} = 1\,099\,511\,627\,776 \\ S(0) &:= 0x600DCAFE & // &= 1\,611\,516\,670 \\ S(n+1) &:= (S(n) + (S(n) \gg 20) + 12345) \bmod M \end{aligned}$$

On the last line, $x \gg 20$ denotes the quotient of the Euclidean division of $x$ by $2^{20}$ and $x \% M$ denotes the remainder of the Euclidean division of $x$ by $M$.

As a very first test to decide if this is indeed a good pseudo-random number generator, Donald wishes to count the number of even values produced by this sequence, in order to check whether this is close enough to 50%. Your help will be welcome.

输入格式

The input consists of a single line, containing an integer $N$.

输出格式

The output should contain a single line with a single integer corresponding to the number of even values in the sequence $S(0), S(1), \ldots, S(N-1)$.

3

2

500000000

250065867

提示

Limits

The input satisfies $0 \leq N < 2^{63}$.