UOJ Logo FLYIOI UOJ

FLYIOI

#19. 单峰排列

问题描述

一个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

时间限制

各测试点1秒

内存限制

你的程序将被分配128MB的运行空间

数据规模

n<=2 000 000 000