You are given a string of digits of length $n$.

Define $f(S)$ as the number of ways to partition $S$ into a sum of several integers, each between $1$ and $m$. For example, when $m=2$, $f(4)=4$, as the partitions are: $4=1+1+1+1, 4=1+1+2, 4=1+2+1, 4=2+1+1, 4=2+2$ (Note: The example in the problem description lists $4=1+1+2, 4=1+2+1, 4=2+1+1, 4=2+2$, implying the sum of $1$s is also considered).

You can split the string of digits into several numbers (leading zeros are allowed), add them together, calculate $f$ for the sum, and find the total sum of these values.

For example, $g(123)=f(1+2+3)+f(1+23)+f(12+3)+f(123)$.

Given the string and $m$, find the answer modulo $998244353$ ($7 \times 17 \times 223 + 1$, a prime number).

Input

The first line contains a string of digits. The second line contains $m$.

Output

Output a single integer representing the answer.

Examples

Input 1

123
3

Output 1

394608467

Constraints

For $30\%$ of the data, the length of the string does not exceed $5$. For $60\%$ of the data, the length of the string does not exceed $18$. For $100\%$ of the data, the length of the string does not exceed $500$, and $m \le 5$.