Logo HelloWorld信息学奥赛题库

少儿编程

时间限制:1 s 空间限制:256 MB

#3022. 「HAOI2015」数字串拆分

统计

题目描述

你有一个长度为 $n$ 的数字串。定义 $f(S)$ 为将 $S$ 拆分成若干个 $1\sim m$ 的数的和的方案数,比如 $m=2$ 时,$f(4)=5$,分别为

$\begin{align} 4 &= 1+1+1+1 \ &= 2+1+1 \ &= 1+2+1 \ &= 1+1+2 \ &= 2+2 \end{align}$

你可以将这个数字串分割成若干个数字(允许前导 $0$),将他们加起来,求 $f$,并求和。比如 $g(123)=f(1+2+3)+f(1+23)+f(12+3)+f(123)$。已知字符串和 $m$ 后求答案对 $998244353$($7 \times 17 \times 223+1$,一个质数)取模后的值。

输入格式

第一行输入一个字符串,第二行输入 $m$。

输出格式

仅输出一个数表示答案。

样例

input

123
3

output

394608467

数据范围与提示

对于 $100 \%$ 的数据,字符串长度不超过 $500$,$m \leq 5$ 。