問題文


頂点 辺のグラフがあります。このグラフの各頂点 について

  • 一様ランダムに頂点 を一つ選び、有向辺 を張る

という操作を行います。このとき、操作によってできる閉路の個数の期待値を で求めてください。

制約


  • 以上 以下の整数

入力


出力


答えを出力し、最後に改行してください。

入力例1

2
出力例1

1

必ず を張ることになるので閉路の個数の期待値は です。

入力例2

3
出力例2

1
入力例3

1000000
出力例3

671367562

提出


Go (1.14)