F - You Got a Wrong Mail

2 secs 1024 MB
Yourein's icon Yourein

Statement

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

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

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

Constraint

  • 1N1061\le N \le 10^6

Input

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

NN

Output

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

Examples

Example1

input1
4
output1
15

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

Example2

input1
124816
output2
732757679

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

提出


Go (1.21)