题目描述

你有一个长度为 $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 2^{23}+1$，一个质数）取模后的值。

---

输入格式

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

---

输出格式

仅输出一个数表示答案。

---

样例

输入

123
3

输出

394608467

---

数据范围与提示

• 字符串长度 $\le 500$
• $m \le 5$