問題文


からまでの整数を並び替えた順列は全部で通りありますが、その全てについて転倒数を求め、総和をで割った余りを答えてください。

制約



・入力は整数である。

入力


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

N

出力


答えを出力してください。

入力例1


3

出力例1


9

の転倒数は
の転倒数は
の転倒数は
の転倒数は
の転倒数は
の転倒数は
です。よって、これらの総和であるを出力します。

入力例2


418269

出力例2


764665541

答えをで割った余りを出力してください。

Submit


Go (1.14)