[AGC052C] Nondivisible Prefix Sums
题意翻译
给定质数 $P$,计数满足以下条件的长度为 $N$ 的序列个数:
- 每一个元素在 $[1,P-1]$ 之间;
- 可以重排这个序列,使得它的任意一个前缀和都不能够被 $P$ 整除。
题目描述
[problemUrl]: https://atcoder.jp/contests/agc052/tasks/agc052_c
素数 $ P $ が与えられます。これはあなたの嫌いな数です。
整数の列 $ A_1,\ A_2,\ \dots,\ A_N $ について、どの接頭辞の和も $ P $ で割り切れないように要素を並べ替えることができるとき、この列を **良い** 列と呼びます(すなわち、並べ替えのあと、$ 1\ \le\ i\ \le\ N $ かつ $ A_1\ +\ A_2\ +\ \dots\ +\ A_i\ \equiv\ 0\ \bmod\ P $ であるような $ i $ が **存在してはいけません**)。
各要素が $ 1 $ 以上 $ P-1 $ 以下であるような長さ $ N $ の整数列は全部で $ (P-1)^N $ 通りありますが、このうち **良い** 列はいくつでしょうか。
答えは非常に大きい可能性があるため、これを $ 998244353 $ で割った余りを出力してください。
输入输出格式
输入格式
入力は以下の形式で標準入力から与えられる。
> $ N $ $ P $
输出格式
**良い** 列の個数を $ 998244353 $ で割った余りを出力せよ。
输入输出样例
输入样例 #1
2 5
输出样例 #1
12
输入样例 #2
4 3
输出样例 #2
8
输入样例 #3
5000 99999989
输出样例 #3
51699346
输入样例 #4
2021 307
输出样例 #4
644635349
说明
### 制約
- $ 1\ \le\ N\ \le\ 5000 $
- $ 2\ \le\ P\ \le\ 10^8 $
- $ P $ は素数である。
### Sample Explanation 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 $ 通りです。
### Sample Explanation 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 $ 通りです。