Problem Description

A sequence of integers with length between $1$ and $N$ (inclusive) and each element between $1$ and $M$ (inclusive) is called a good sequence.

The score of a good sequence is defined as the total number of positive divisors of $X$, where $X$ is the product of all elements in the sequence.

There are $\displaystyle\ \sum_{k=1}^{N}M^k$ good sequences. Find the sum of the scores of all these sequences modulo $998244353$.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $

Output Format

Output the answer as an integer.

Sample Input and Output

Sample Input #1

1 7

Sample Output #1

16

Sample Input #2

3 11

Sample Output #2

16095

Sample Input #3

81131 14

Sample Output #3

182955659

Notes/Hints

Constraints

• $1\ \leq\ N\ \leq\ 10^{18}$
• $1\ \leq\ M\ \leq\ 16$
• All inputs are integers

Sample Explanation 1

There are $7$ 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 Explanation 2

For example, $(8, 11)$ and $(1, 8, 2)$ are good sequences. Here is the process of calculating their scores:
- The product of elements in $(8, 11)$ is $8 \times 11 = 88$. The positive divisors of $88$ are $1, 2, 4, 8, 11, 22, 44, 88$, so the score of $(8, 11)$ is $8$.
- The product of elements in $(1, 8, 2)$ is $1 \times 8 \times 2 = 16$. The positive divisors of $16$ are $1, 2, 4, 8, 16$, so the score of $(1, 8, 2)$ is $5$.

Sample Explanation 3

Remember to find the answer modulo $998244353$.

见题面 Input 部分

见题面 Output 部分