凹形队列

时间限制：1秒　　内存限制：256M

---

【题目描述】

　　所谓的凹形队列，就是一个 \(1 \sim N\) 的全排列 \(P_1,P_2,…,P_N\) ，当且仅当存在某个 \(k\) 使得：

　　　　　　　\(P_1 > P_2 > ... > P_k < P_{k+1} < ... < P_N\)

　　比如 \(N=7\) 时，那么全排列，7631245 是凹形队列，7654321 也是凹形队列，当然，1234567也是凹形队列，但 3562147 就不是。

　　请编程，输入 \(N\) ，输出凹形队列的个数。

【输入格式】

　　一个正数 \(N\)。

【输出格式】

　　输出 \(1 \sim N\) 的全排列中凹形队列的个数 \(mod\ 1234567\) 的值。

【输入输出样例】

　Input

4

　Output

8

【数据限制】

　　对于 \(100\%\) 的数据，\(1≤N≤2×10^9\)。

【来源】

　　Mr.he