Busy Beaver 正在修習圖論課程，他的老師要求他計算滿足特定條件的圖的數量。請幫他解決這個關於圖計數的問題！

令 $P$ 為一個奇質數，$N$ 為一個正整數。請計算頂點數為 $NP$ 的無向標記簡單圖中，不包含長度為 $P$ 的簡單環的圖的數量。請將答案對 $P$ 取模。請注意此敘述中 $P$ 的重複出現！

無向圖中的簡單環是指一個不重複使用任何頂點的環。

輸入格式

輸入為一行，包含兩個整數：$P$ ($3 \le P < 5000$) 與 $N$ ($1 \le N \le 10^9$)。$P$ 是一個奇質數。

輸出格式

輸出一個對 $P$ 取模後的整數。

子任務

• (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 的簡單環，因此總共有 7 個圖不包含長度為 3 的簡單環。接著，7 對 3 取模的結果為 1。

註記

在第一個範例中，我們計算頂點數為 $1 \cdot 3 = 3$ 的標記圖中，不包含長度為 3 的簡單環的數量。在總共 $2^3 = 8$ 個圖中，恰好有一個圖包含長度為 3 的簡單環，因此總共有 7 個圖不包含長度為 3 的簡單環。接著，7 對 3 取模的結果為 1。