時間制限 : sec, メモリ制限 : KB
Japanese

H: Permutation Score

問題文

松崎くんは順列が大好きです。今日は順列によって定まる「サイクル森」について考えることにしました。

$1$ から $k$ までの順列 $p = (p_1, \ldots, p_k)$ に対し「$p$ によって定まるサイクル森」とは、以下の2条件を満たすグラフ $G(p)$ を指します:

  • $G(p)$ は $k$ 頂点からなり、それぞれの頂点には $1$ から $k$ の番号が付けられている。
  • $i=1, \ldots, k$ について、頂点 $i$ と頂点 $p_i$ の間に辺が張られている(自己ループおよび多重辺を許し、必ず $k$ 本の辺を張る)。逆に、$G(p)$にはそれら $k$ 本以外の辺は存在しない。

順列 $p$ のスコア $f(p)$ を、「$G(p)$ の連結成分の大きさの総積」として定義します。例えば $p = (2, 1, 4, 3)$ ならば $f(p) = 4$、$p = (2, 3, 1, 4)$ ならば $f(p) = 3$です。

正整数 $N$ が与えられます。長さ $N$ の順列は $N!$ 通り考えられますが、これら全ての順列のスコアの分散はいくつになるか求めてください。

全ての順列のスコアの分散とは以下のように定義されます:

  1. まず、$P$ を $N!$ 個の順列全てからなる集合とします。
  2. スコアの平均を$a = \frac{1}{N!} \sum_{p \in P} f(p)$ とおきます。
  3. この時、全ての順列のスコアの分散は $\frac{1}{N!} \sum_{p \in P} (f(p) - a)^2$ として定義されます。

入力の制約下において、求める値は以下の条件を満たす有理数 $\frac{q}{p}$ として表せることが証明できます:

  • $p$ と $q$ は互いに素な非負整数である。
  • $p$ は $10^9+7$ の倍数にならず、$p \cdot r \equiv q (\bmod 10^9+7)$ なる整数 $r$が存在する。

分散の値の代わりに $r \bmod 10^9+7$を出力してください。

制約

  • 入力は全て整数
  • $1 \leq N \leq 10^5$

入力

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

$N$

出力

問題文中で指定された値 $r \bmod 10^9+7$ を1行に出力してください。

入出力例

入力例1

1

出力例1

0

長さ1の順列は1つのみであり、分散は0になります。

入力例2

3

出力例2

472222226

分散の値は $\frac{17}{36}$ですが、問題文中の指示に従って $17 \times 27777778 \bmod 10^9+7 = 472222226$ を出力してください。

入力例3

10

出力例3

309669455