G: Donuts Orientation

物語

ほむちゃんの最近のマイブームはお菓子作りだ。たくさんお菓子を作っては、それを友達におすそ分けしているらしい。そんなほむちゃんは今回、ドーナツづくりに挑戦するようだ。

ドーナツづくりに大切なことはいくつもある。生地や味付けはもちろん、かわいい見た目にするためのデコレーションも外せない。試行錯誤を繰り返しているうちに、ほむちゃんのデコレーションへのこだわりに熱がこもってきたようだ。こだわりぬいたドーナツを多くの人に食べてもらいたいので、ほむちゃんはドーナツをたくさんつくりたいと考えている。

・・・ところで、こだわるのは一向に構わないが、ほむちゃんこだわりのドーナツを十分な数用意することはできるのだろうか？

問題

3 以上の整数 N について、以下のようにして 2N 頂点のグラフを作る。

このグラフの各辺に向きをつけて、有向グラフを作る。つまり、頂点 u と v の間に無向辺があるならば、それを u から v へ向かう有向辺にするか、v から u へ向かう有向辺にする。

このようにしてできた有向グラフであって、サイクルを持たないものが何通りあるかを知りたい。答えは非常に大きくなるため、素数 M で割った余りを求めよ。

入力形式

N M

制約

出力形式

条件を満たす有向グラフの数を M で割った余りを出力せよ。

入力例1

3 1000000007

出力例1

204

N = 3 なので、6 頂点からなるグラフを作る。条件に合致する有向グラフの一例は以下の通りである。

サイクルが存在するため、以下に示す有向グラフは条件を満たさない。

入力例2

128 998244353

出力例2

996915100

M で割った余りを出力することに注意せよ。