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

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

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

样例如下：

in : 0145217 7

out : 16