P16791 [蓝桥杯 2026 国 A] 神秘排列

小蓝在研究组合数学时，提出了“平衡位置”的概念。 对于 $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$ 取模后的结果。

### 【样例说明】 当 $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$。