/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1000 点
問題文
素数 P が与えられます。これはあなたの嫌いな数です。
整数の列 A_1, A_2, \dots, A_N について、どの接頭辞の和も P で割り切れないように要素を並べ替えることができるとき、この列を 良い 列と呼びます（すなわち、並べ替えのあと、1 \le i \le N かつ A_1 + A_2 + \dots + A_i \equiv 0 \bmod P であるような i が 存在してはいけません）。
各要素が 1 以上 P-1 以下であるような長さ N の整数列は全部で (P-1)^N 通りありますが、このうち 良い 列はいくつでしょうか。
答えは非常に大きい可能性があるため、これを 998244353 で割った余りを出力してください。
制約
- 1 \le N \le 5000
- 2 \le P \le 10^8
- P は素数である。
入力
入力は以下の形式で標準入力から与えられる。
N P
出力
良い 列の個数を 998244353 で割った余りを出力せよ。
入力例 1
2 5
出力例 1
12
良い列は [1, 1], [1, 2], [1, 3], [2, 1], [2, 2], [2, 4], [3, 1], [3, 3], [3, 4], [4, 2], [4, 3], [4, 4] の 12 通りです。
入力例 2
4 3
出力例 2
8
良い列は [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] の 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