题目描述

给定一个素数 $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

输入

2 5

输出

12

样例 2

输入

4 3

输出

8

样例 3

输入

5000 99999989

输出

51699346

样例 4

输入

2021 307

输出

644635349

说明/提示

限制条件

• $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 翻译