题目描述

小蓝在研究组合数学时，提出了“平衡位置”的概念。

对于 $1$ 到 $n$ 的一个排列 $a_1, a_2, \ldots, a_n$，如果位置 $i$ 满足以下条件，则称位置 $i$ 是平衡位置：

• “在位置 $i$ 左侧，数值小于 $a_i$ 的元素个数”恰好等于“在位置 $i$ 右侧，数值大于 $a_i$ 的元素个数”。

其中，位置 $i$ 左侧指位置 $1, 2, \ldots, i-1$，位置 $i$ 右侧指位置 $i+1, i+2, \ldots, n$，左侧、右侧均不包含位置 $i$ 本身。

小蓝认为，如果一个排列中至少有 $\lceil n/2 \rceil$ 个平衡位置（$\lceil x \rceil$ 表示向上取整），那么这个排列就被称为一个“好排列”。

现在，给定数字 $n$，请你计算 $1$ 到 $n$ 的所有排列中，好排列的数量。由于答案可能很大，请输出其对 $10^9 + 7$ 取模后的结果。

输入格式

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

输出格式

输出一行，一个整数，表示好排列数量对 $10^9 + 7$ 取模后的结果。

4

7

提示

【样例说明】

当 $n = 4$ 时，一个好排列至少需要 $\lceil 4/2 \rceil = 2$ 个平衡位置。

以排列 $4\ 3\ 2\ 1$ 为例：每个位置左侧都没有比当前位置元素更小的数，右侧也没有比当前位置元素更大的数，因此四个位置都是平衡位置。该排列是一个好排列。

长度为 $4$ 的所有排列中，共有 $7$ 个好排列，因此输出 $7$。

【评测用例规模与约定】

对于 $30\%$ 的评测用例，$1 \le n \le 10$。

对于 $60\%$ 的评测用例，$1 \le n \le 5000$。

对于所有评测用例，$1 \le n \le 10^7$。