Statement

小さな村のある郵便局に区別できる$N$通の手紙があります。手紙には差出人と宛名が書いてありますが、すべての手紙についてどちらも雨に濡れて読めなくなってしまいました。しかし、どの手紙も村の人間から村の人間にあてられた手紙であることだけはわかります。
この村に住む人は相互にとても仲が良いので、あなたは手紙をランダムに届け、各人から正しい人に届けてもらうことにしました。

ところで村には$N$人が住んでおり、実は$i (1 \le i \le N)$番目の手紙は人$i$に届くはずのものでした。
あなたが一人1枚ずつランダムに手紙を届けた時、1軒以上本来の届け先に正しく手紙を届けられるような届け方は何通りありますか?(このような届け方の例は入力例1を参考にしてください)

答えは非常に大きくなる可能性があるので$10^9+7$で割ったあまりを求めてください。

Constraint

• $1\le N \le 10^6$

Input

入力は以下の形式で与えられる

Output

条件を満たすような手紙の配り方の総数を$10^9+7$で割ったあまりを答えよ

Examples

Example1

4

15

例えば$i = 1$から順に$(2, 3, 1, 4)$というような届け方をすると4軒目には正しく配送できています。
1, 2, 3軒目は間違っていますが、1件以上届け先が正しいのでこのような届け方も答えに含みます。

Example2

124816

732757679

$10^9+7$で割ることを忘れないでください。