Busy Beaver はグラフ理論の授業を受けており、先生からある特別な条件を満たすグラフの数を数えるように言われました。グラフの数え上げに関する以下の問題を解くのを手伝ってあげてください！

$P$ を奇素数、$N$ を正の整数とします。$NP$ 個の頂点を持つ無向ラベル付き単純グラフのうち、長さ $P$ の単純サイクルを含まないものの数を数えてください。答えを $P$ で割った余りを求めてください。この問題文における $P$ の繰り返しに注意してください！

無向グラフにおける単純サイクルとは、どの頂点も二度以上使用しないサイクルのことです。

入力

入力は1行で、2つの整数 $P$ ($3 \le P < 5000$) と $N$ ($1 \le N \le 10^9$) が与えられます。$P$ は奇素数です。

出力

$P$ で割った余りを1つの整数で出力してください。

小課題

• (25点) $N \le P$ かつ $P \le 500$。
• (25点) $N \le P$。
• (25点) $P \le 500$。
• (25点) 追加の制約なし。

入出力例

入力 1

3 1

出力 1

1

入力 2

5 4

出力 2

1

入力 3

479 166

出力 3

344

注記

最初のサンプルでは、$1 \cdot 3 = 3$ 個の頂点を持つラベル付きグラフのうち、長さ 3 の単純サイクルを持たないものの数を数えています。全 $2^3 = 8$ 通りのグラフのうち、長さ 3 の単純サイクルを含むものはちょうど 1 つであるため、条件を満たすグラフは 7 通りとなります。したがって、$7 \pmod 3$ は 1 です。