Description

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$.

Input Format

The first line contains a string, which represents $s_0$.

The second line contains an integer, which represents $m$.

Output Format

Output a single integer representing the answer.

123
3

394608467

Hint

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