205011 - 单峰排列

一个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的全排列中单峰排列的个数% 1 234 567的值。

共有以下4种方案：

123
132
231
321