序列划分

题目描述 给一个长度为�的数字串�，你想把它划分成若干段连续的子串，一共有2�−1 种划 分方法。

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

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

输入格式 一行，一个数字串�和数字�。

输出格式 输出一个数，表示答案。

样例输入 1 0145217 7

样例输出 1 16

样例解释 所有 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 满足，|�| ≤ 20。

测试点 2,3 满足，|�| ≤ 1000。 测试点 4,5,6 满足，(�, 10) = 1。

对于 100%的数据，满足|�| ≤ 5 × 105 , 1 ≤ � ≤ 106 。