#arc163d. [arc163_d]Sum of SCC
[arc163_d]Sum of SCC
問題文
以下の条件を全て満たす頂点に から までの番号がついた 頂点の有向グラフ を考えます。
-
はトーナメントである。すなわち、 に多重辺や自己ループはなく、 のどの 頂点 に対しても、 辺または 辺のうちちょうど片方が存在する。
-
の辺のうち、頂点番号が小さい方から大きい方へ向けられた辺はちょうど 本存在する。
そのような有向グラフ 全てに対する強連結成分の個数の総和を で割ったあまりを求めてください。
制約
入力
入力は以下の形式で標準入力から与えられる。
出力
答えを出力せよ。
入力例 1
出力例 1
条件を満たす有向グラフ は以下の 個です。それぞれ強連結成分の個数は であるため答えは です。