你有一个长度为 的数字串 。
定义 为将 拆分成若干个 的数的和的方案数，比如 时，，分别为 。
定义 为将 这个数字串分割成若干个数字（允许前导 ），设他们的和为 ，则 为所有情况下 之和。比如 。
给定 和 ，求 。
答案对 取模。
第一行有一个字符串。代表 。
第二行有一个整数，代表 。
仅输出一个数表示答案。
123 3
394608467
