#P3176. [HAOI2015] 数字串拆分

[HAOI2015] 数字串拆分

题目描述

你有一个长度为 nn 的数字串 s0s_0

定义 f(s)f(s) 为将 ss 拆分成若干个 1m1 \sim m 的数的和的方案数,比如 m=2m=2 时,f(4)=5f(4)=5,分别为 4=1+1+1+1=1+1+2=1+2+1=2+1+1=2+24=1+1+1+1=1+1+2=1+2+1=2+1+1=2+2

定义 g(s)g(s) 为将 ss 这个数字串分割成若干个数字(允许前导 00),设他们的和为 xx,则 g(s)g(s) 为所有情况下 f(x)f(x) 之和。比如 g(123)=f(1+2+3)+f(1+23)+f(12+3)+f(123)g(123)=f(1+2+3)+f(1+23)+f(12+3)+f(123)

给定 s0s_0mm,求 g(s)g(s)

答案对 998,244,353998,244,353 取模。

输入格式

第一行有一个字符串。代表 s0s_0

第二行有一个整数,代表 mm

输出格式

仅输出一个数表示答案。

123
3
394608467

提示

数据规模与约定

  • 对于 100%100\% 的数据,保证 1s05001\le|s_0|\le 5001m51\le m\le 5s0s_0 中只有数字字符。