1661: 测算字串
金币值：2
定数：1
时间限制：1.000 s
内存限制：128 M
正确：0
提交：0
正确率：0.00% 命题人：
题目描述
设字符集的大小为k 。请计算满足以下所有要求的字符串的数量：
• 长度为n
• 每一个字符都属于字符集
• 不存在长度为k的子串，在其中出现全部k种字符
其 中 ，字 符 串的子串定义为字符串中连续的一段字符 。例如，字符串heavenburnsred 的子串有he 、venbur 、d等等，但hbr不是它的子串。
由于答案可能很大，你只需要输出答案除以998244353所得的余数。
输入格式
输入包含1行2个整数n, k，含义见题目描述。
数据范围如下：
• 2 ≤ k ≤ 100
• k ≤ n ≤ 109
• 有30%的数据，n ≤ 10000, k ≤ 7
• 有20%的数据，n ≤ 50000
输出格式
输出1行1个整数表示答案。
输入样例 复制
7 7输出样例 复制
818503提示
样例解释：
对于样例1，字符集中有7种不同的字符，长度为7的字符串共有77个。其中不合要求的字符串都是7个字 符的一个排列，有7!个，故答案是77 - 7! = 818503 。