(C++）人字排列问题，求指点迷津

Question

一个1到n的排列被称为人字排列，是指排列中的第1到第（n+1）/2个元素单调递增，第（n+1）/2到n个元素单调递减例如：（2，3，5，8，9，7，6，4，1）是一个人字排列，而（1，2，3）
和1，3）都不是人字排列，（2，4，3）也不是一个人字排列（甚至不是一个1到4的排列）
请问，1到n的排列中有多少个人字排列？
输入格式
输入一行包含一个奇数n输出格式
输出
一行包含一个整数，表示答案，答案可能很大，请输出答案除以1000000007的余数
样例输入
5
样例输出
6
样例说明
（1，2，5，4，3）（1，3，5，4，2）（1，4，5，3，2）
（2、3、5、4、1）（2、4、5、3、1）（3、4、5、2、1）

Answer 1

我觉得是这样的，原理是12345这五个数字，你把5放在最中间，剩下的分成两组，比如说分成12 5 34，那么要是人字形的话就只能是12543的情况了，所以问题的核心是怎么把四个数分成两组。联系一下排列组合的知识，相当于4个里面选两个，也就是C42，所以直接想办法如何用n来表示C(n-1)(n-1)/2。