测试数据来自 system/1878

作业已超过截止时间，您无法递交本题目。

凹形队列

时间限制：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