题目描述

江桥喜欢做数学题！

对于一个正整数，江桥求出其所有数位上的数字的和 $a$ 和所有非 $0$ 数位的最小公倍数 $b$。

江桥发现，对于某些数字满足 $b|a = 0$，即所有非 $0$ 数位上数字的最小公倍数能被所有数位上的数字和整除。

江桥想知道，对于 $[1,n]$ 内的所有整数，有多少数字的非 $0$ 数位上数字的最小公倍数恰好为 $m$，且能被其所有数位上的数字和整除。

形式化题意：

设某正整数的数位表示为 $\overline{d_k d_{k-1}d_{k-2}...d_1}$，令 $a = \sum_{i = 1}^kd_i$，$b = \sum_{i = 1,d_i \neq 0}^{k}lcm(d_i)$。

求 $[1,n]$ 内的整数数量满足 $b = m$ 且 $a \equiv 0$ $mod$ $m$。保证 $n$ 是 $10$ 的整数次方 $-1$。

由于答案可能过大，你需要输出答案对 $10^9+7$ 取模后的值。

输入格式

一行两个正整数 $n,m$，含义如上所述。

输出格式

一个非负整数 $ans$，表示答案对 $10^9+7$ 取模后的值。

9 4

1

样例解释

满足条件的数字只有 $4$。

数据规模与约定

下发文件

下发文件分别对应子任务 $1$、$4$。

有合理的子任务依赖。

对于 $100\%$ 的数据：保证 $1 \leq n \leq 10^{100},1 \leq m \leq 10^{18},\exists k > 0,n = 10^k - 1$。