问题描述
一个n的全排列A[i]是单峰的，当且仅当存在某个x使得A[1]< A[2]< ...< A[x]>A[x+1]>...>A[n]。
例如，对于9的全排列，125798643是一个单峰排列，123456789也是一个单峰排列，但356298741就不是。
试求n的单峰全排列的个数。
输入数据
输入一个数n。
输出数据
输出n的全排列中单峰排列的个数。
由于这个数可能很大，因此你只需要输出它mod 1234567的值。
输入样例 3 输出样例 4样例说明
共有以下4种方案：
123
132
231
321
数据规模
n<=2 000 000 000