/ 
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 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) の 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) の要素の総積は 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
81131 14
出力例 3
182955659
998244353 で割った余りを求めることを忘れないでください。
Score : 600 points
Problem Statement
An integer sequence of length between 1 and N, inclusive, where each element is between 1 and M, inclusive, is called a good sequence.
The score of a good sequence is defined as the number of positive divisors of X, where X is the product of the elements in the sequence.
There are \displaystyle \sum_{k=1}^{N}M^k good sequences. Find the sum of the scores of all those sequences modulo 998244353.
Constraints
- 1 \leq N \leq 10^{18}
- 1 \leq M \leq 16
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M
Output
Print the answer as an integer.
Sample Input 1
1 7
Sample Output 1
16
There are seven good sequences: (1),(2),(3),(4),(5),(6),(7). Their scores are 1,2,2,3,2,4,2, respectively, so the answer is 1+2+2+3+2+4+2=16.
Sample Input 2
3 11
Sample Output 2
16095
For example, (8,11) and (1,8,2) are good sequences. Here is the process of calculating their scores:
- The product of the elements in (8,11) is 8 \times 11 = 88. 88 has eight positive divisors: 1,2,4,8,11,22,44,88, so the score of (8,11) is 8.
- The product of the elements in (1,8,2) is 1 \times 8 \times 2 = 16. 16 has five positive divisors: 1,2,4,8,16, so the score of (1,8,2) is 5.
Sample Input 3
81131 14
Sample Output 3
182955659
Remember to take the result modulo 998244353.