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

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

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

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

输出一个数，表示答案。

样例1：
0145217 7

样例2：
100100 10

样例1：
16

样例2：
30

样例1解释
所有 16 种划分方案：0145217,0 145217,0 14 5217,0 14 5 217,0 14 5 21 7,014521 7,0 145 217,0 145 21 7,0 14521 7,014 5217,014 5 217,014 5 21 7,014 5217,0145 217,0145 21 7,014521 7。

数据规模
共十组数据。
测试点 1 满足，|S| ≤ 20。
测试点 2,3 满足，|S| ≤ 1000。
测试点 4,5,6 满足，(D, 10) = 1。
对于 100% 的数据，满足 |S| ≤ 5 × 10^5, 1 ≤D ≤ 10^6 。