Contest Duration: - (local time) (160 minutes) Back to Home
C - Nondivisible Prefix Sums /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

• 1 \le N \le 5000
• 2 \le P \le 10^8
• P は素数である。

### 入力

N P


### 入力例 1

2 5


### 出力例 1

12


### 入力例 2

4 3


### 出力例 2

8


### 入力例 3

5000 99999989


### 出力例 3

51699346


### 入力例 4

2021 307


### 出力例 4

644635349


Score : 1000 points

### Problem Statement

You are given a prime number P, which you don't like.

Let's call an array of integers A_1, A_2, \dots, A_N good, if it is possible to reorder the elements in such a way that no prefix sum is divisible by P (that is, there is no i with 1 \le i \le N and A_1 + A_2 + \dots + A_i \equiv 0 \bmod P after the reordering).

Consider all (P-1)^N arrays of length N with elements from 1 to P-1. How many of them are good?

As this number can be very big, output it modulo 998244353.

### Constraints

• 1 \le N \le 5000
• 2 \le P \le 10^8
• P is a prime.

### Input

Input is given from Standard Input in the following format:

N P


### Output

Output the number of good arrays modulo 998244353.

### Sample Input 1

2 5


### Sample Output 1

12


There are 12 good arrays: [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 4], [3, 1], [3, 3], [3, 4], [4, 2], [4, 3], [4, 4].

### Sample Input 2

4 3


### Sample Output 2

8


There are 8 good arrays: [1, 1, 1, 2], [1, 1, 2, 1], [1, 2, 1, 1], [2, 1, 1, 1], [2, 2, 2, 1], [2, 2, 1, 2], [2, 1, 2, 2], [1, 2, 2, 2].

### Sample Input 3

5000 99999989


### Sample Output 3

51699346


### Sample Input 4

2021 307


### Sample Output 4

644635349