MojaCoder国は から までの番号のついた 個の都市からなり、都市間は何本かの、双方向に運行する鉄道路線で結ばれています。 鉄道旅行が好きなriano君は、この国で以下のような条件を満たす旅をしたいと考えています。
MojaCoder国の鉄道路線の詳細は分かっていませんが、
ことが分かっています。 この時、考えられる鉄道の路線整備状況(別の言葉で言えば、単純な無向グラフ)は全部で 通りありますが、このうちriano君が上記の条件を満たす旅を実現できるものは何通りでしょうか。 で答えてください。
答えを で割った余りを出力してください。
4
5
例えば図のように鉄道路線が存在している場合、riano君は →→→→ という旅程で目的を達成することができます。 このようなものは全部で つあります。
また、下記の「正答に含まれない図」のように、同じ つの都市間に つの路線がある場合や、旅程の中で全ての都市を訪れることができない場合は数えないよう注意してください。
600
796105666
で答えてください。