406699: GYM102501 H Pseudo-Random Number Generator

H. Pseudo-Random Number Generatortime limit per test0.3 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output 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 the right are comments). $$$$$$ \begin{array}{rlr} M &:= 1 \ll 40 & // = 2^{40} = 1 099 511 627 776\\ S(0)&:= 0x600\text{DCAFE} &// = 1 611 516 670\\ S(n + 1) &:= (S (n) + ( S(n ) \gg 20) + 12345)\% M& \end{array} $$$$$$ 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.

Input

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

Limits

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

Output

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)$$$.

ExamplesInput

3

Output

2

Input

500000000

Output

250065867