题目背景

Special for beginners, ^_^

题目描述

小明得到一个只包含数字的字符串。他想把这个字符串分割成若干段，每一段表示一个整数。

但有两个限制：

每一段的数字 不能有前导零（除非这一段就是 "0"）。

每一段表示的整数 不能超过 K。

小明想知道，一共有多少种不同的分割方法。

给定一个数字字符串 s 和一个整数 𝐾

请计算把字符串 𝑠分割成若干合法整数的方案数。

输入格式

第一行：

s

第二行：

K

数据范围：

1 ≤ |s| ≤ 20 1 ≤ K ≤ 10^9

输出格式

输出一个整数，表示分割方案数。

样例

1234
34

5

样例解释

合法分割：

1 | 2 | 3 | 4 1 | 2 | 34 1 | 23 | 4 12 | 3 | 4 12 | 34

这些数都 ≤ 34。

所以答案是 5。