← 返回题目列表

AtCoder · agc052_c

C. 不可整除的前缀和

中文机器翻译题面 查看原题

分数: 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