ほむちゃんの最近のマイブームはお菓子作りだ。たくさんお菓子を作っては、それを友達におすそ分けしているらしい。そんなほむちゃんは今回、ドーナツづくりに挑戦するようだ。
ドーナツづくりに大切なことはいくつもある。生地や味付けはもちろん、かわいい見た目にするためのデコレーションも外せない。試行錯誤を繰り返しているうちに、ほむちゃんのデコレーションへのこだわりに熱がこもってきたようだ。こだわりぬいたドーナツを多くの人に食べてもらいたいので、ほむちゃんはドーナツをたくさんつくりたいと考えている。
・・・ところで、こだわるのは一向に構わないが、ほむちゃんこだわりのドーナツを十分な数用意することはできるのだろうか？
3 以上の整数 N について、以下のようにして 2N 頂点のグラフを作る。
このグラフの各辺に向きをつけて、有向グラフを作る。つまり、頂点 u と v の間に無向辺があるならば、それを u から v へ向かう有向辺にするか、v から u へ向かう有向辺にする。
このようにしてできた有向グラフであって、サイクルを持たないものが何通りあるかを知りたい。答えは非常に大きくなるため、素数 M で割った余りを求めよ。
N M
条件を満たす有向グラフの数を M で割った余りを出力せよ。
3 1000000007
204
N = 3 なので、6 頂点からなるグラフを作る。条件に合致する有向グラフの一例は以下の通りである。
サイクルが存在するため、以下に示す有向グラフは条件を満たさない。
128 998244353
996915100
M で割った余りを出力することに注意せよ。