题目描述

有 $N$ 个格子横向排列，从左到右编号为 $1$ 到 $N$。最初，所有格子都是白色的。另外，有 $N-1$ 台涂色机器，编号为 $1$ 到 $N-1$。涂色机器 $i$ 启动时，会将第 $i$ 个格子和第 $i+1$ 个格子涂成黑色。

すぬけ君将依次启动这些涂色机器。すぬけ君启动机器的顺序由 $1$ 到 $N-1$ 的一个排列 $P$ 给出。也就是说，第 $i$ 次启动的机器编号为 $P_i$。

对于某个排列 $P$，其得分定义为：按照该顺序依次启动机器，首次所有格子都被涂成黑色时，已经启动的机器数量。すぬけ君还没有决定排列 $P$，但他对得分感兴趣。请你计算所有排列的得分之和。由于答案可能很大，请输出对 $10^9+7$ 取模的结果。

输入格式

输入为一行，包含一个整数 $N$。

输出格式

请输出所有排列 $P$ 的得分之和，对 $10^9+7$ 取模。

样例 1

输入

4

输出

16

样例 2

输入

2

输出

1

样例 3

输入

5

输出

84

样例 4

输入

100000

输出

341429644

说明/提示

限制

• $2 \leq N \leq 10^6$

样例解释 1

所有可能的排列 $P$ 有 $6$ 种。在这些排列中，只有 $P = (1, 3, 2)$ 或 $P = (3, 1, 2)$ 时得分为 $2$，其余排列得分为 $3$。因此，答案为 $2 \times 2 + 3 \times 4 = 16$。

样例解释 2

唯一可能的排列是 $P = (1)$，得分为 $1$。

由 ChatGPT 4.1 翻译