1933: 单峰排列

【题目描述】

一个n的全排列A[i]是单峰排列，当且仅当存在某个x使得A[1]＜A[2]＜…＜A[x]＞A[x＋1]＞…＞A[n]。

例如：对于9的全排列，125 798 643和123 456 789是单峰排列，但356 298 741就不是。

试求n的全排列中，有多少个单峰排列。

【输入格式】

输入一个数n（整型范围）。

【输出格式】

输出n的全排列中单峰排列的个数对1234567取模后的值。

【输入样例】

3

【输出样例】

4

【样例说明】

共有以下4种方案：

123

132

231

321

3

4