One-way and Once a Way

2 secs 1024 MB
riano_

問題文


MojaCoder国は から までの番号のついた 個の都市からなり、都市間は何本かの、双方向に運行する鉄道路線で結ばれています。 鉄道旅行が好きなriano君は、この国で以下のような条件を満たす旅をしたいと考えています。

  • 都市 から出発して都市 で旅を終える
  • 全ての都市を一度以上訪れる(出発地や最終目的地も含む。また、二度以上訪れる都市があってもよい)
  • MojaCoder国に存在する鉄道路線を全て、一度だけ経由する
  • MojaCoder国内の都市間の移動は全て鉄道で行う

MojaCoder国の鉄道路線の詳細は分かっていませんが、

  • 全ての鉄道は、異なる つの都市間を双方向に結ぶ路線として運行しており、途中で他の都市を経由しない
  • 任意の 都市間において、これらを直接結ぶ鉄道路線は 本以上運行していない

ことが分かっています。 この時、考えられる鉄道の路線整備状況(別の言葉で言えば、単純な無向グラフ)は全部で 通りありますが、このうちriano君が上記の条件を満たす旅を実現できるものは何通りでしょうか。 で答えてください。

制約


  • 入力は全て整数である

入力


出力


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

サンプル


入力1
4
出力1
5

例えば図のように鉄道路線が存在している場合、riano君は という旅程で目的を達成することができます。 このようなものは全部で つあります。

図

また、下記の「正答に含まれない図」のように、同じ つの都市間に つの路線がある場合や、旅程の中で全ての都市を訪れることができない場合は数えないよう注意してください。

図

入力2
600
出力2
796105666

で答えてください。

Submit


Go (1.14)