入力1個数え上げ

2 secs 1024 MB
bachoppi

問題文


あなたは、の数字を各回ずつ好きな順で計回、すなわち順列になるように言うことができます。
最初の持ち点は点で、回目に数字を言うとき、以下のルールに従って得点が加算されます。(回目に言う数字をと表記します)

  • のときは、得点は加算されない
  • のとき、点加算される

ルールを満たす数字の言い方は通りありますが、そのうち最終得点が最大になるようなものは何通りありますか。 で割った余りを求めてください。

制約


  • 入力はすべて整数

入力


N

出力


得点が最大になる場合の数をで割った余りを出力してください。

サンプル


入力1
3
出力1
3

最終得点の最大値は点です。 通りがこの得点になります。

入力2
4
出力2
4
入力3
1000000
出力3
924863273

提出


Go (1.14)