分数: 1000 点
问题陈述
给你一个素数 P,你不喜欢。
让我们调用一个整数数组 A_1, A_2, \dots, A_N 好,如果可以以没有前缀和可以整除的方式对元素重新排序 P (也就是说,有 no i 与 1 \le i \le N 和 A_1 + A_2 + \dots + A_i \equiv 0 \bmod P 重新排序后)。
考虑所有 (P-1)^N 长度数组 N 的元素来自 1 to P-1。其中有多少人 好?
由于这个数字可能很大,所以输出它的模 998244353.
约束
- 1 \le N \le 5000
- 2 \le P \le 10^8
- P 是质数。
输入
输入由标准输入按以下格式给出:
N P
输出
输出数量 好 数组取模 998244353.
示例输入 1
2 5
示例输出 1
12
有 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].
示例输入 2
4 3
示例输出 2
8
有 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].
示例输入 3
5000 99999989
示例输出 3
51699346
示例输入 4
2021 307
示例输出 4
644635349