[AGC023C] Painting Machines

- 有一排 $n$ 个格子，从左到右编号为 $1$ 到 $n$。 - 有 $n - 1$ 个机器，从左到右编号为 $1$ 到 $n - 1$，操作第 $i$ 个机器可以将第 $i$ 个和第 $i + 1$ 个格子染黑。 - 定义一个 $n - 1$ 的排列 $P$ 的分数为，依次操作 $P_1,P_2,\cdots,P_{n-1}$，第一次染黑所有格子的时刻。 - 求所有排列 $P$ 的分数之和，对 $10^9 + 7$ 取模。 - $1\le n\le 10^6$.

[problemUrl]: https://atcoder.jp/contests/agc023/tasks/agc023_c $ N $ 個のマスが横一列に並んでおり、左から右へ $ 1 $ から $ N $ までの番号がついています。 最初、すべてのマス目は白いです。 また、$ N-1 $ 台のペイントマシンがあり、$ 1 $ から $ N-1 $ までの番号が付けられています。 ペイントマシン $ i $ は、稼働すると、マス $ i $ とマス $ i+1 $ を黒く塗ります。 すぬけ君は、これらのペイントマシンを、$ 1 $ 台ずつ順番に稼働させます。 すぬけくんがマシンを稼働させる順番は、$ (1,\ 2,\ ...,\ N-1) $ の順列 $ P $ によって表されます。 これは、$ i $ 番目に稼働させるマシンの番号が $ P_i $ であることを意味します。 ここで、ある順列 $ P $ のスコアは、その順列に従ってマシンを稼働させたとき、 すべてのマスが黒く塗られた状態に初めてなるまでに稼働させたマシンの台数と定義されます。 すぬけ君はまだ順列 $ P $ を決めていませんが、スコアに興味があります。 すぬけ君のために、すべての順列についてそのスコアを求め、その総和を求めてください。 ただし、答えは非常に大きくなることがあるので、$ 10^9\ +7 $ で割った余りを求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $

すべての順列 $ P $ のスコアの総和を $ 10^9\ +\ 7 $ で割った余りを出力せよ。

4

16

2

1

5

84

100000

341429644

### 制約 - $ 2\ \leq\ N\ \leq\ 10^6 $ ### Sample Explanation 1 順列 $ P $ としてありうるものは $ 6 $ つあります。 この中で、$ P\ =\ (1,\ 3,\ 2) $ または $ P\ =\ (3,\ 1,\ 2) $ のときだけスコアは $ 2 $ になり、 それ以外のときはスコアは $ 3 $ になります。 よって、求める答えは $ 2\ \times\ 2\ +\ 3\ \times\ 4\ =\ 16 $ となります。 ### Sample Explanation 2 ありうる唯一つの順列は $ P\ =\ (1) $ で、スコアは $ 1 $ です。