给定一个仅包含数字 '0' 到 '9' 的字符串 S，求有多少种方式按顺序取 S 的部分位得到一的整数是 $M$ 的倍数。精确地讲，按顺序取 $S$ 一部分是指根据 $1≤a_1<a_2<...<a_k≤|S|$ 取出一个整数 $S[a_1]S[a_2]...S[a_k]$。其中，$S[i]$ 表示字符串 $S$ 的第 $i$ 个字符。
从不同位置取出相同的整数，算成不同的方案。例如 $S$ 是 "110" 时，取第一位第三位得到 $10$，取第二位第三位也得到 $10$，如果 $M=2$，这算两种不同的方式。但是，取出来的数不能是 "0" 开头。例如 $S$ 是 "102" 时，不能取出 "02" 作为 $2$ 的倍数。
由于答案可能很大，只需要输出答案 mod $10^9+7$ 的结果。

第一行一个字符串 $S$。
第二行一个整数 $M$。

一个整数，表示答案。

对于 20% 的数据，|S|≤16，M≤1000。
对于 48% 的数据，|S|≤10000，M≤1000。
对于 100% 的数据，|S|≤10000，M≤20000。

7

第一个 2、第二个 2、0、22、第一个 2 和 0 形成的 20、第二个 2 形成的 20、220 是满足条件的。

262143

$2^{18}-1=262143$