Background

回老家吃饭导致的

Description

$2n$ 个人围成一个圆桌，每两个人形成一个组合，要求他们距离为 $m$ ,问在 $1$ 到 $n$ 的范围内有多少个 $m$ 满足条件， 对 $1226999999$ 取模

Format

Input

一个整数 $n$

Output

满足条件个数，不同 $n$ 相同 $m$ 重复计数

Sample 1

Input

4

Output

9

Limitation

对于 $20\%$ 的数据

$n \le 10^2$

对于 $50\%$ 的数据

$n \le 10^3$

对于 $70\%$ 的数据

$n \le 10^6$

对于 $100\%$ 的数据

$n \le 10^{18}$

Hint

$n=1$ , $m=1$
$n=2$ , $m=1,2$
$n=3$ , $m=1,3$
$n=4$ , $m=1,2,3,4$