ほむちゃんは、そーるじぇむを赤色や黒色に変化させたり、 異なる 2 つのそーるじぇむ間を魔法の糸で接続したりする不思議な力を持っています。 この力を使うことで、ほむちゃんは、そーるじぇむによる魔方陣を作ることができます。
ほむちゃんは、 1 から N で番号付けられた N 個のそーるじぇむがあるとき、以下の条件が成り立つ異なる魔方陣がいくつあるのか気になりました。
このとき、魔方陣はそーるじぇむを頂点とし、魔法の糸を辺とするグラフとみなすことができます。 ここで、そのグラフは 連結でなくてもよい ことに注意してください。
ほむちゃんは計算が苦手なので、代わりにあなたが高速なプログラムを作って異なる魔方陣の数を計算してあげましょう。 しかし、その数は非常に多いことが予想されるので、ある素数 M で割った余りを求めることにします。
なお、ある魔方陣 G と H が異なるとは、あるそーるじぇむ v について G と H でその色が異なる、もしくはあるそーるじぇむの組 u, v が G と H の一方でのみ接続されていることを指します。
N M
条件を満たすグラフの個数を M で割った余りを整数で 1 行に出力してください。
3 310779401
12
例えば、以下のような魔方陣は条件を満たします。
7 566666561
98638848
例えば、以下のような魔方陣は条件を満たします。
1010 1000000007
862232855
M で割った余りを出力することに注意してください。