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

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

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

作为判断这是否确实是一个好的伪随机数生成器的初步测试，Donald 希望统计该序列中偶数值的数量，以检查其是否足够接近 50%。欢迎你提供帮助。

输入格式

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

数据范围

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

输出格式

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

样例

样例输入 1

3

样例输出 1

2

样例输入 2

500000000

样例输出 2

250065867