Digit String Partition Sums

You are given a digit string s_0 of length n and an integer m. Consider the following definitions:

• Define f(x) as the number of ways to write the positive integer x as a sum of one or more numbers chosen from the set \(\{1,2,\dots,m\}\). Formally, f(0)=1 and for any x \ge 1, \[ f(x)=\sum_{i=1}^{\min(m,x)} f(x-i). \] For example, when m = 2, we have f(4)=5 because \[ 4=1+1+1+1=1+1+2=1+2+1=2+1+1=2+2. \]
• Define g(s) for a digit string s as follows: partition s into one or more contiguous substrings (each substring is interpreted as a decimal number and may have leading zeros), let the sum of these numbers be \(x\), and then take f(x). The value g(s) is the sum of f(x) over all possible partitions of s. For example, for s = "123", the partitions and their corresponding sums are:
  "1", "2", "3" → \(1+2+3=6\);
  "1", "23" → \(1+23=24\);
  "12", "3" → \(12+3=15\);
  "123" → \(123\).
  Thus, g(123)=f(6)+f(24)+f(15)+f(123).

Your task is to compute g(s_0) modulo 998244353.

inputFormat

The input consists of two lines:

• The first line contains the digit string s_0.
• The second line contains the integer m.

outputFormat

Output a single integer, the value of g(s_0) modulo 998244353.

sample

12
2

236