[HAOI 2015] 数字串拆分

• 时间限制：1 秒
• 内存限制：128 MiB

题目描述

给定正整数 $m$，定义 $f(x)$ 为把非负整数 $x$ 表示成若干个 $1$ 到 $m$ 的整数之和的有序方案数，并规定 $f(0)=1$。

给定数字串 $s$。你可以在相邻字符之间任选若干位置切开，得到若干个允许含前导零的十进制整数。设这些整数之和为 $x$。定义 $g(s)$ 为所有切分方案对应的 $f(x)$ 之和。

例如，$g(123)=f(1+2+3)+f(1+23)+f(12+3)+f(123)$。

请输出 $g(s)$ 对 $998244353$ 取模的结果。

输入格式

第一行输入数字串 $s$，第二行输入整数 $m$。

输出格式

输出一个整数表示答案。

样例输入

123
3

样例输出

394608467

数据范围

对于所有数据，$1\le|s|\le500$，$1\le m\le5$，$s$ 只含数字字符。