Pseudo-Random Number Generator#9709

Pseudo-Random Number Generator

1 second

128 megabytes

Easy

Donald loves nature. Being a programmer, he develops programs to simulate the growth of trees and to construct realistic three-dimensional landscapes. For these purposes, Donald needs a reliable pseudorandom number generator. He proposes the following method for constructing an infinite sequence of unsigned $40$ -bit integers.

m := 1 << 40 // = 2^40 = 1 099 511 627 776
S(0) := 0x600DCAFE // = 1 611 516 670
S(n + 1) := (S(n) + (S(n) >> 20) + 12345) % m

In the last line, the operation $x >> 20$ x >> 20 denotes the integer quotient of the Euclidean division of $x$ by $2^{20}$ 2^{20}, and the operation $x % m$ denotes the remainder of the Euclidean division of $x$ by $m$ .

As a first test to evaluate the quality of the pseudorandom number generator, Donald wants to count the number of even values produced by this sequence and check how close this proportion is to $50%$ . Your help would be greatly appreciated.

Input

A single integer $n (0 \leq n < 2^{63})$ n~(0 \le n < 2^{63}).

Output

Print one integer — the number of even values among the elements of the sequence $S (0), S (1), \dots, S (n - 1)$ S(0), S(1), \ldots, S(n - 1).

Examples

Example 1

Example 2