题目描述

给定一个素数 $P$，你不喜欢它。

如果一个整数数组 $A_1, A_2, \\dots, A_N$ 可以被重新排序，使得没有前缀和能够被 $P$ 整除（即，在重新排序后，不存在 $i$ 满足 $1 \\le i \\le N$ 和 $A_1 + A_2 + \\dots + A_i \\equiv 0 \\bmod P$），我们称之为好的。

考虑所有由 $1$ 到 $P-1$ 的元素组成的长度为 $N$ 的数组，共有多少个数组是好的？

由于这个数字可能非常大，对 $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