半递增序列 ### 题目描述 一个 $1$ 到 $n$ 的排列被称为半递增序列，是指排列中的奇数位置上的值单调递增，偶数位置上的值也 单调递增。 　 例如：$(1, 2, 4, 3, 5, 7, 6, 8, 9)$ 是一个半递增序列，因为它的奇数位置上的值是 $1, 4, 5, 6, 9$，单调递增，偶数位置上的值是 $2, 3, 7, 8$，也是单调递增。 　 请问，$1$ 到 $n$ 的排列中有多少个半递增序列？ ### 输入描述 输入的一行包含一个正整数 $n$。 　 ### 输出描述 输出一行包含一个整数，表示答案，答案可能很大，请输出答案除以 $1000000007$ 的余数。 ### 输入输出样例 #### 示例 >输入 ```txt 5 ``` >输出 ```txt 10 ``` ### 样例说明 有以下半递增序列： 　 $(1, 2, 3, 4, 5)$ $(1, 2, 3, 5, 4) $　 $(1, 2, 4, 3, 5) $ $(1, 3, 2, 4, 5) $ $(1, 3, 2, 5, 4) $ $(1, 4, 2, 5, 3) $ $(2, 1, 3, 4, 5) $ $(2, 1, 3, 5, 4) $ $(2, 1, 4, 3, 5)$　 $(3, 1, 4, 2, 5)$ ### 评测用例规模与约定 对于 $50$% 的评测用例，$2 \leq n \leq 20$。 　 对于所有评测用例，$2 \leq n \leq 1000$。