配点 : $600$ 点

問題文

正整数 $N, M$ が与えられます。 頂点に $1, \dots, N$ の番号が付けられた $N$ 頂点の単純連結無向グラフであって、以下の条件を満たすものの総数を $M$ で割った余りを求めてください。

• 全ての $u = 2, \dots, N-1$ について、頂点 $1$ から頂点 $u$ までの最短距離は、頂点 $1$ から頂点 $N$ までの最短距離より真に小さい。

ただし、頂点 $u$ から頂点 $v$ までの最短距離とは、頂点 $u, v$ を結ぶ単純パスに含まれる辺の本数の最小値を指します。 また、$2$ つのグラフが異なるとは、ある $2$ 頂点 $u, v$ が存在して、これらの頂点を結ぶ辺が一方のグラフにのみ存在することを指します。

制約

• $3 \leq N \leq 500$
• $10^8 \leq M \leq 10^9$
• $N, M$ は整数

入力

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

$N$ $M$

出力

答えを出力せよ。

4 1000000000

8

以下の $8$ 通りが条件を満たします。

3 100000000

1

500 987654321

610860515

$M$ で割った余りを求めることに注意してください。