AT_agc052_c [AGC052C] Nondivisible Prefix Sums

给定一个素数 $P$，这是你讨厌的数字。 对于一个整数序列 $A_1,\ A_2,\ \dots,\ A_N$，如果可以重新排列这些元素，使得任意前缀和都不能被 $P$ 整除（即，重新排列后，对于所有 $1 \le i \le N$，都不存在 $A_1 + A_2 + \dots + A_i \equiv 0 \pmod{P}$），那么称这个序列为**好**序列。 长度为 $N$ 的整数序列，每个元素都在 $1$ 到 $P-1$ 之间（包含 $1$ 和 $P-1$），这样的序列一共有 $(P-1)^N$ 种。请问其中有多少个**好**序列。 由于答案可能非常大，请输出其对 $998244353$ 取模的结果。

输入从标准输入中给出，格式如下： > $N$ $P$

输出**好**序列的个数对 $998244353$ 取模的结果。

## 限制条件 - $1 \le N \le 5000$ - $2 \le P \le 10^8$ - $P$ 是素数。 ## 样例解释 1 好序列有 $[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 好序列有 $[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$ 种。 由 ChatGPT 4.1 翻译