← 返回题目列表

AtCoder · agc023_c

C. 喷漆机

中文机器翻译题面 查看原题

分数: 800 点

问题陈述

有 N 方块排成一排,编号 1 通过 N 从左到右。 最初,所有方块都是白色的。 我们还有 N-1 喷漆机,编号 1 通过 N-1。 操作时,机器 i 油漆广场 i 和 i+1 黑色。

Snuke 将一一操作这些机器。 他操作它们的顺序由以下排列表示 (1, 2, ..., N-1), P,这意味着 i第一个操作的机器是机器 P_i.

这里, 排列的 分数 本实验的 的排列 P 被定义为当机器按照指定的顺序操作时,所有方格第一次被涂成黑色之前操作的机器数量 P。 Snuke还没有决定什么排列 P 使用,但他对可能的排列的分数感兴趣。 求他所有可能排列的分数总和。 由于这可能非常大,因此计算总和模 10^9+7.

约束

  • 2 \leq N \leq 10^6

输入

输入由标准输入按以下格式给出:

N

输出

打印所有可能排列的分数总和,模 10^9+7.


示例输入 1

4

示例输出 1

16

有六种可能的排列: P。 其中, P = (1, 3, 2) 和 P = (3, 1, 2) 的得分为 2,其他人的得分为 3。 因此,答案是 2 \times 2 + 3 \times 4 = 16.


示例输入 2

2

示例输出 2

1

只有一种可能的排列: P = (1),其得分为 1.


示例输入 3

5

示例输出 3

84

示例输入 4

100000

示例输出 4

341429644