Moon is a primary school student who encountered the following problem while doing homework: given positive integers $n$ and $k$, calculate the value of the following expression:

$$\sum_{i=1}^{n} \frac{i!}{i^k}$$

Here, $i!$ denotes the factorial of $i$, i.e., $i! = 1 * 2 * 3 * 4 * ... * i$. This expression is too difficult, so Moon hopes to get your help. However, because Moon has only learned integer arithmetic and not real number arithmetic, he hopes you can help him find the value of this expression modulo $998244353$. That is, if the final result is simplified to the irreducible fraction $\frac{p}{q}$, you only need to output $p * q^{-1} \pmod{998244353}$, where $q^{-1}$ is the modular multiplicative inverse of $q$ modulo $998244353$.

Input

The first line contains two integers $n$ and $k$.

Output

A single line containing an integer representing the answer modulo $998244353$.

Examples

Input 1

5 1

Output 1

34

Note 1

In Example 1, since $i!/i = (i - 1)!$, the original expression is equivalent to $\sum_{i=1}^{5} (i - 1)! = 34$.

Input 2

100 100

Output 2

523011929

Input 3

10000000 10000000

Output 3

686183373

Constraints

For all data, $1 \le n, k \le 2 * 10^7$; For 30% of the data, $k = 1$; For another 30% of the data, $1 \le k \le 3$.