E. K-Sufficient Numbers

Time Limit: 2 seconds

Memory Limit: 1024 MB

Rating: 1900

Problem Statement

Edward has come up with a new category of numbers, the sufficient numbers! The set of $K$-sufficient numbers contains all integers whose digits sum to $K$. Compute the $N$-th smallest $K$-sufficient number modulo $998244353$. If there is no such number, output $-1$. $1 \le N \le 10^{12}$ $1 \le K \le 10{,}000$

Input

The first line has two space-separated integers $N$ and $K$.

Output

Output the answer.

Sample Cases
Sample Input 1:
10000 5

Sample Output 1:
632106520


Sample Input 2:
2 4

Sample Output 2:
13
Explanation

Remember to output the answer modulo $998244353$.

Sources

IanOJ Contest #3 (Div. 2) > Problem E

Submit | Back