你有一个长度为 nnn 的数字串。定义 f(S)f(S)f(S) 为将 SSS 拆分成若干个 1 m1~m1 m 的数的和的方案数,比如 m=2m=2m=2 时,f(4)=5f(4)=5f(4)=5,分别为
4=1+1+1+1=2+1+1=1+2+1=1+1+2=2+2
你可以将这个数字串分割成若干个数字(允许前导 000),将他们加起来,求 fff,并求和。比如 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)g(123)=f(1+2+3)+f(1+23)+f(12+3)+f(123)。已知字符串和 mmm 后求答案对 998244353998244353998244353(7×17×223+17 \times 17 \times 223+17×17×223+1,一个质数)取模后的值。
第一行输入一个字符串,第二行输入mmm。
仅输出一个数表示答案
123 3
394608467
对于 100%100 \%100% 的数据,字符串长度不超过 500500500,m≤5m \leq 5m≤5