题目描述

给一个长度为 $n$ 的数字串 $S$ ，你想把它划分成若干段连续的子串，一共有 $2^{n−1}$ 种划 分方法。

给一个整数 $D$ ，你希望划分方案中，如果我们把每个子串当作一个十进制下的数字 （可以有前导 $0$ ），那么不存在两个相邻的子串不被 $D$ 整除。

输出方案总数，对 $10^9 +7$ 取模的结果。

输入格式

一行，一个数字串 $S$ 和数字 $D$ 。

输出格式

输出一个数，表示答案。

样例 1 输入

0145217 7

样例 1 输出

16

样例 1 解释

所有 $16$ 种划分方案：0145217,0 145217,0 14 5217,0 14 5 217,0 14 5 21 7,0 14 521 7,0 145 217,0 145 21 7,0 14521 7,014 5217,014 5 217,014 5 21 7,014 521 7,0145 217,0145 21 7,014521 7。

样例 2 输入

100100 10

样例 2 输出

30

样例 3 输入输出

见下发文件。

数据规模

共十组数据。

测试点 $1$ 满足， $|S| ≤ 20$ 。

测试点 $2,3$ 满足， $|S| ≤ 1000$ 。

测试点 $4,5,6$ 满足， $\gcd(D, 10) = 1$ 。

对于 $100\%$ 的数据，满足 $|S| ≤ 5 × 10^5, 1 ≤ D ≤ 10^6$ 。