F: 赤黒そーるじぇむ / Red-Black Soul Gem

問題

ほむちゃんは、そーるじぇむを赤色や黒色に変化させたり、 異なる 2 つのそーるじぇむ間を魔法の糸で接続したりする不思議な力を持っています。 この力を使うことで、ほむちゃんは、そーるじぇむによる魔方陣を作ることができます。

ほむちゃんは、 1 から N で番号付けられた N 個のそーるじぇむがあるとき、以下の条件が成り立つ異なる魔方陣がいくつあるのか気になりました。

このとき、魔方陣はそーるじぇむを頂点とし、魔法の糸を辺とするグラフとみなすことができます。 ここで、そのグラフは 連結でなくてもよい ことに注意してください。

ほむちゃんは計算が苦手なので、代わりにあなたが高速なプログラムを作って異なる魔方陣の数を計算してあげましょう。 しかし、その数は非常に多いことが予想されるので、ある素数 M で割った余りを求めることにします。

なお、ある魔方陣 G と H が異なるとは、あるそーるじぇむ v について G と H でその色が異なる、もしくはあるそーるじぇむの組 u, v が G と H の一方でのみ接続されていることを指します。

入力形式

N M

制約

出力形式

条件を満たすグラフの個数を M で割った余りを整数で 1 行に出力してください。

入力例1

3 310779401

出力例1

12

例えば、以下のような魔方陣は条件を満たします。

入力例2

7 566666561

出力例2

98638848

例えば、以下のような魔方陣は条件を満たします。

入力例3

1010 1000000007

出力例3

862232855

M で割った余りを出力することに注意してください。