分数: 600 点
问题陈述
长度介于 1 和 N,包含在内,其中每个元素位于 1 和 M,包含在内,被称为 好的序列.
的 分数 一个好序列的 被定义为 X,其中 X 是序列中元素的乘积。
有 \displaystyle \sum_{k=1}^{N}M^k 好的序列。求所有这些序列的模分数之和 998244353.
约束
- 1 \leq N \leq 10^{18}
- 1 \leq M \leq 16
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M
输出
将答案打印为整数。
示例输入 1
1 7
示例输出 1
16
有七个好的序列: (1),(2),(3),(4),(5),(6),(7)。他们的分数是 1,2,2,3,2,4,2分别,所以答案是 1+2+2+3+2+4+2=16.
示例输入 2
3 11
示例输出 2
16095
例如, (8,11) 和 (1,8,2) 是很好的序列。以下是计算分数的过程:
- 中元素的乘积 (8,11) is 8 \times 11 = 88. 88 有八个正因数: 1,2,4,8,11,22,44,88,所以分数 (8,11) is 8.
- 中元素的乘积 (1,8,2) is 1 \times 8 \times 2 = 16. 16 有五个正因数: 1,2,4,8,16,所以分数 (1,8,2) is 5.
示例输入 3
81131 14
示例输出 3
182955659
记住对结果取模 998244353.