半递增序列

题目描述

一个 $1$ 到 $n$ 的排列被称为半递增序列，是指排列中的奇数位置上的值单调递增，偶数位置上的值也 单调递增。 　

例如：$(1, 2, 4, 3, 5, 7, 6, 8, 9)$ 是一个半递增序列，因为它的奇数位置上的值是 $1, 4, 5, 6, 9$，单调递增，偶数位置上的值是 $2, 3, 7, 8$，也是单调递增。 　

请问，$1$ 到 $n$ 的排列中有多少个半递增序列？

输入描述

输入的一行包含一个正整数 $n$。 　

输出描述

输出一行包含一个整数，表示答案，答案可能很大，请输出答案除以 $1000000007$ 的余数。

输入输出样例

示例

>输入

5

>输出

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$。