3149: 单峰
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：19
解决：13
题目描述
⼩ X 归来后，⾸先对数列很感兴趣。他想起有⼀类特殊的数列叫单峰数列。 我们说⼀个数列 {a i } 是单峰的， 当且仅当存在⼀个位置 k 使得 a i < a i+1 (i < k) 且 a i > a i+1 (i ≥ k)。 现在⼩ X 想知道，对于 1 到 n 的所有排列，其中有多少个是单峰数列。
输入
第一行包含一个整数 n。
输出
第一行包含一个整数，表示答案除以 10^ 9 + 7 的余数。
样例输入 复制
2样例输出 复制
2提示
• 对于 20% 的数据，n ≤ 10。 • 对于 50% 的数据，n ≤ 10^ 5 。 • 对于 100% 的数据，2 ≤ n ≤ 10^ 18 。