说明

Donald 热爱自然。作为一名程序员，Donald 编写程序来模拟树木的生长或构建逼真的 3D 景观。为此，Donald 需要一个良好的伪随机数生成器。他设计了以下方法来生成一个无限序列的 40 位无符号整数（绿色行为注释）。

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

在最后一行中，$x \gg 20$ 表示 $x$ 除以 $2^{20}$ 的欧几里得除法的商，而 $x \% M$ 表示 $x$ 除以 $M$ 的欧几里得除法的余数。

作为决定这是否真的是一个良好的伪随机数生成器的第一个测试，Donald 希望计算该序列产生的偶数值的数量，以检查这是否足够接近 50%。你的帮助将非常受欢迎。

输入格式

输入仅包含一行，包含一个整数 $N$。

输出格式

输出应包含一行，包含一个整数，对应序列 $S(0), S(1), \ldots, S(N-1)$ 中偶数值的数量。

3

2

500000000

250065867

提示

数据范围

输入满足 $0 \leq N < 2^{63}$。

翻译由 DeepSeek 完成