AT_agc065_f [AGC065F] Always Perfect

[problemUrl]: https://atcoder.jp/contests/agc065/tasks/agc065_f 偶数 $ N $ および素数 $ M $ が与えられます。 $ 1 $ から $ N $ までの番号が付いた $ N $ 頂点からなる単純連結無向グラフ $ G $ のうち、以下の条件を満たすものの個数を $ M $ で割った余りを求めてください。 - $ G $ の任意の全域木 $ T $ に対し、$ T $ 上の完全マッチングが存在する。 グラフの完全マッチングとは？ グラフ $ G $ に対し、 $ G $ の辺からなる集合 $ E $ であって、グラフ上のすべての頂点 $ v $ に対し、 $ v $ を端点とする辺がちょうど $ 1 $ つ $ E $ に含まれるようなものを $ G $ 上の完全マッチングとよびます。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $

答えを出力せよ。

### 制約 - $ 2\ \leq\ N\ \leq\ 500 $ - $ 10^8\ \leq\ M\ \leq\ 10^9 $ - $ N $ は偶数 - $ M $ は素数 - 入力される値はすべて整数 ### Sample Explanation 1 例えば下図で示された $ 2 $ つのグラフについて、左側のグラフは条件を満たします。一方、右側のグラフは赤い太線で示された $ 3 $ 辺からなる全域木上には完全マッチングが存在しないため、条件を満たしません。 !\[\](https://img.atcoder.jp/agc065/2ef467c5e79ec3372986afd95c28100a.png)