AT_arc182_c [ARC182C] Sum of Number of Divisors of Product

题目描述

我们称长度在 $1$ 到 $N$ 之间、每个元素在 $1$ 到 $M$ 之间的整数序列为良好数列。

对于一个良好数列，其得分定义为该序列所有元素的乘积 $X$ 的正约数个数。

良好数列共有 $\displaystyle\sum_{k=1}^{N} M^k$ 个，请你求出所有良好数列得分的总和，并对 $998244353$ 取余。

输入格式

输入以如下格式从标准输入读入。

$N$ $M$

输出格式

请输出答案的整数值。

样例 1

输入

1 7

输出

16

样例 2

输入

3 11

输出

16095

样例 3

输入

81131 14

输出

182955659

说明/提示

限制条件

• $1 \leq N \leq 10^{18}$
• $1 \leq M \leq 16$
• 输入均为整数

样例解释 1

良好数列有 $(1),(2),(3),(4),(5),(6),(7)$ 共 $7$ 个。它们的得分分别为 $1,2,2,3,2,4,2$，因此 $1+2+2+3+2+4+2=16$，答案为 $16$。

样例解释 2

例如 $(8,11)$ 或 $(1,8,2)$ 都是良好数列。计算这些数列的得分过程如下：

• $(8,11)$ 的元素乘积为 $8\times 11=88$。$88$ 的正约数有 $1,2,4,8,11,22,44,88$ 共 $8$ 个，因此 $(8,11)$ 的得分为 $8$。
• $(1,8,2)$ 的元素乘积为 $1\times 8\times 2=16$。$16$ 的正约数有 $1,2,4,8,16$ 共 $5$ 个，因此 $(1,8,2)$ 的得分为 $5$。

样例解释 3

不要忘记对 $998244353$ 取余。

由 ChatGPT 4.1 翻译