#2128. 「HAOI2015」数字串拆分

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

你有一个长度为 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

输出格式

仅输出一个数表示答案。

样例

样例输入

123
3

样例输出

394608467

数据范围与提示

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