1302: #2128. 「HAOI2015」数字串拆分

Memory Limit:256 MB Time Limit:1.000 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

你有一个长度为 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 后求答案对 9982443539982443539982443537×17×223+17 \times 17 \times 223+17×17×223+1,一个质数)取模后的值。

输入格式

第一行输入一个字符串,第二行输入mmm

输出格式

仅输出一个数表示答案

样例

样例输入

123
3

样例输出

394608467

数据范围与提示

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