시간 제한메모리 제한제출정답맞힌 사람정답 비율
0.3 초 512 MB58181431.111%

## 문제

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

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

On the last line, x >> 20 denotes the quotient of the Euclidean division of x by 220 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), . . . , S(N − 1).

## 제한

The input satisfies 0 ≤ N < 263.

## 예제 입력 1

3


## 예제 출력 1

2


## 예제 입력 2

500000000


## 예제 출력 2

250065867