問題文


以上 以下の整数の中から相異なる つの整数 を選びます。ただし、次の条件を満たさなくてはなりません。

条件:

つの半開区間 が共通区間を持たないような の選び方は何通りでしょうか。 答えを で割ったあまりを出力してください。

制約


入力


入力はすべて整数である。

N

出力


問題文にあるような の選び方の総数を で割ったあまりを出力してください。

サンプル


入力1
4
出力1
2

の場合、 の 2 通りです。

入力2
30
出力2
54810

提出


Go (1.14)