問題文


頂点のラベル付き完全グラフであって、各辺の重みが のいずれかであるようなものは全部で 個ありますが、それらの最小全域木の重みの総和を で割った余りを求めてください。

  

制約


  •   

入力


入力は以下の形式で標準入力から与えられます。

  

出力


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

  

入力例1


1

出力例1


3

全ての辺の重みが であるような 頂点の完全グラフの最小全域木の重みは です。  
 

入力例2


2

出力例2


226

最小全域木の重みが となるものが 個、 となるものが 個、 となるものが 個、 となるものが 個あります。
よって、重みの総和は です。ところで、私の誕生日は 日です。 
 

入力例3


178096

出力例3


714149329

で割った余りを求めることを忘れずに。

提出


Go (1.14)