#AGC023C. [AGC023C] Painting Machines

[AGC023C] Painting Machines

配点 : 800800

問題文

NN 個のマスが横一列に並んでおり、左から右へ 11 から NN までの番号がついています。 最初、すべてのマス目は白いです。 また、N1N-1 台のペイントマシンがあり、11 から N1N-1 までの番号が付けられています。 ペイントマシン ii は、稼働すると、マス ii とマス i+1i+1 を黒く塗ります。

すぬけ君は、これらのペイントマシンを、11 台ずつ順番に稼働させます。 すぬけくんがマシンを稼働させる順番は、(1,2,...,N1)(1, 2, ..., N-1) の順列 PP によって表されます。 これは、ii 番目に稼働させるマシンの番号が PiP_i であることを意味します。

ここで、ある順列 PP のスコアは、その順列に従ってマシンを稼働させたとき、 すべてのマスが黒く塗られた状態に初めてなるまでに稼働させたマシンの台数と定義されます。 すぬけ君はまだ順列 PP を決めていませんが、スコアに興味があります。 すぬけ君のために、すべての順列についてそのスコアを求め、その総和を求めてください。 ただし、答えは非常に大きくなることがあるので、109+710^9 +7 で割った余りを求めてください。

制約

  • 2N1062 \leq N \leq 10^6

入力

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

NN

出力

すべての順列 PP のスコアの総和を 109+710^9 + 7 で割った余りを出力せよ。

4
16

順列 PP としてありうるものは 66 つあります。 この中で、P=(1,3,2)P = (1, 3, 2) または P=(3,1,2)P = (3, 1, 2) のときだけスコアは 22 になり、 それ以外のときはスコアは 33 になります。 よって、求める答えは 2×2+3×4=162 \times 2 + 3 \times 4 = 16 となります。

2
1

ありうる唯一つの順列は P=(1)P = (1) で、スコアは 11 です。

5
84
100000
341429644