1299: #2128. 「HAOI2015」数字串拆分
[Creator : ]
Description
你有一个长度为 $n$ 的数字串。定义 f(S) 为将 $S$ 拆分成若干个 $1 \sim m$ 的数的和的方案数,比如 $m=2$ 时,$f(4)=5$,分别为
$4=1+1+1+1=2+1+1=1+2+1=1+1+2=2+2$
你可以将这个数字串分割成若干个数字(允许前导 $0$),将他们加起来,求fff,并求和。
比如 $g(123)=f(1+2+3)+f(1+23)+f(12+3)+f(123)$。
已知字符串和 $m$ 后求答案对 $998244353\ (7 \times 17 \times 223+1)$,一个质数,取模后的值。
$4=1+1+1+1=2+1+1=1+2+1=1+1+2=2+2$
你可以将这个数字串分割成若干个数字(允许前导 $0$),将他们加起来,求fff,并求和。
比如 $g(123)=f(1+2+3)+f(1+23)+f(12+3)+f(123)$。
已知字符串和 $m$ 后求答案对 $998244353\ (7 \times 17 \times 223+1)$,一个质数,取模后的值。
Input
第一行输入一个字符串,第二行输入 $m$。
Output
仅输出一个数表示答案。
Constraints
对于 $100\%$ 的数据,字符串长度不超过 $500$,$m≤5$。
Sample 1 Input
123
3
Sample 1 Output
394608467