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