P3176 [HAOI2015] Digit String Partition

You have a digit string $s_0$ of length $n$. Define $f(s)$ as the number of ways to split $s$ into a sum of numbers in the range $1 \sim m$. For example, when $m=2$, $f(4)=5$, namely $4=1+1+1+1=1+1+2=1+2+1=2+1+1=2+2$. Define $g(s)$ as follows: split the digit string $s$ into several numbers (leading $0$ are allowed), let their sum be $x$, then $g(s)$ is the sum of $f(x)$ over all such cases. For example, $g(123)=f(1+2+3)+f(1+23)+f(12+3)+f(123)$. Given $s_0$ and $m$, compute $g(s_0)$. Take the answer modulo $998,244,353$.

The first line contains a string, which represents $s_0$. The second line contains an integer, which represents $m$.

Output a single integer representing the answer.

#### Constraints and Conventions - For $100\%$ of the testdata, it is guaranteed that $1 \le |s_0| \le 500$, $1 \le m \le 5$, and $s_0$ contains only digit characters. Translated by ChatGPT 5