首先考虑 $(D,10) = 1$ 的情况，记 $S_i = (∑S_i ⋅ 10^{|s| −i} ) \mod D$ ，也就是从 $i$ 这个位置到 结尾的值，那么 $s[i …j]$ 能被 $D$ 整除，当且仅当 $S_i =S_{j+1}$ 。

记 $dp_{i,0/1}$ 表示前往后，划分到i ，当前段能否被 $D$ 整除，那么如果当前段能被整除， 那么必须从 $S_j = S_{i+1}$ 转移过来，否则从不被整除的位置转移过来，记录一下 $S_j$ 等于某个值的 $dp$ 值之和，从前往后转移即可。

如果 $(D , 10) ≠ 1$ ，那么上面的条件不成立。令 $D = D_1D_2$ ，其中 $D_1$ 与 $10$ 互质，$D_2$ 里只包含因子 $2,5$ ，令 $S_i$ 表示从 $i$ 这个位置到结尾的值对 $D_1$ 取模，那么$S_[i…j]$ 能被 $D$ 整除，当且仅当 $S_i = S_{j+1}$ ，且这个数能被 $D_2$ 整除。在十进制下，被 $2,5$ 的幂次整除，我们只需要看后若干位即可，这里$D$ 不是很大，所以只需要看后 20 位。所以类似于上面的 $dp$ 。从前面的位置j转移到i ，如果j已经小于 $i − 20$ ，并且后 $20$ 满足条件，那么用上述的方法转移即可。对于$i− 20 ∼ i − 1$ ，暴力判断转移即可。

时间复杂度是 $O(nlogD)$。

#include <bits/stdc++.h>

using namespace std;

template <typename T>
T power(T a, long long b) {
	T r = 1;
	while (b) {
		if (b & 1) {
			r *= a;
		}
		a *= a;
		b >>= 1;
	}
	return r;
}

template <typename T>
T inverse(T a, T m) {
	a %= m;
	if (a < 0) {
		a += m;
	}
	T b = m, u = 0, v = 1;
	while (a) {
		T t = b / a;
		b -= a * t;
		swap(a, b);
		u -= v * t;
		swap(u, v);
	}
	if (u < 0) {
		u += m;
	}
	return u;
}

template <int _P>
struct modnum {
		static constexpr int P = _P;

	private:
		int v;

	public:
		modnum() : v(0) {
		}

		modnum(long long _v) {
			v = _v % P;
			if (v < 0) {
				v += P;
			}
		}

		explicit operator int() const {
			return v;
		}

		bool operator==(const modnum &o) const {
			return v == o.v;
		}

		bool operator!=(const modnum &o) const {
			return v != o.v;
		}

		modnum inverse() const {
			return modnum(::inverse(v, P));
		}

		modnum operator-() const {
			return modnum(v ? P - v : 0);
		}

		modnum operator+() const {
			return *this;
		}

		modnum &operator++() {
			v++;
			if (v == P) {
				v = 0;
			}
			return *this;
		}

		modnum &operator--() {
			if (v == 0) {
				v = P;
			}
			v--;
			return *this;
		}

		modnum operator++(int) {
			modnum r = *this;
			++*this;
			return r;
		}

		modnum operator--(int) {
			modnum r = *this;
			--*this;
			return r;
		}

		modnum &operator+=(const modnum &o) {
			v += o.v;
			if (v >= P) {
				v -= P;
			}
			return *this;
		}

		modnum operator+(const modnum &o) const {
			return modnum(*this) += o;
		}

		modnum &operator-=(const modnum &o) {
			v -= o.v;
			if (v < 0) {
				v += P;
			}
			return *this;
		}

		modnum operator-(const modnum &o) const {
			return modnum(*this) -= o;
		}

		modnum &operator*=(const modnum &o) {
			v = (int) ((long long) v * o.v % P);
			return *this;
		}

		modnum operator*(const modnum &o) const {
			return modnum(*this) *= o;
		}

		modnum &operator/=(const modnum &o) {
			return *this *= o.inverse();
		}

		modnum operator/(const modnum &o) const {
			return modnum(*this) /= o;
		}
};

template <int _P>
ostream &operator<<(ostream &out, const modnum<_P> &n) {
	return out << int(n);
}

template <int _P>
istream &operator>>(istream &in, modnum<_P> &n) {
	long long _v;
	in >> _v;
	n = modnum<_P>(_v);
	return in;
}

using num = modnum<1000000007>;

int main() {
	freopen("division.in", "r", stdin);
	freopen("division.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(0);
	string s;
	int d;
	cin >> s >> d;
	int e = 1;
	while (d % 2 == 0) {
		d /= 2;
		e *= 2;
	}
	while (d % 5 == 0) {
		d /= 5;
		e *= 5;
	}
	int n = s.size();
	vector<int> a(n + 1);
	for (int i = 0; i < n; ++i) {
		a[i + 1] = (a[i] * 10 + (s[i] - '0')) % (d * e);
	}
	int inv10 = d == 1 ? 0 : inverse(10, d);
	vector<int> pw(n + 1);
	pw[0] = 1;
	for (int i = 0; i < n; ++i) {
		pw[i + 1] = (long long) pw[i] * inv10 % d;
	}
	vector<int> base(20);
	base[0] = 1;
	for (int i = 0; i + 1 < 20; ++i) {
		base[i + 1] = base[i] * 10 % (d * e);
	}
	vector<num> foo(n + 1), bar(n + 1);
	vector<num> offset_foo(d), offset_bar(d);
	bar[0] = 1;
	num pref = 0;
	for (int i = 0; i <= n; ++i) {
		foo[i] += pref;
		if (a[i] % e == 0) {
			foo[i] += offset_foo[(long long) a[i] * pw[i] % d];
			bar[i] += offset_bar[(long long) a[i] * pw[i] % d];
		}
		pref += bar[i];
		offset_foo[(long long) a[i] * pw[i] % d] -= bar[i];
		offset_bar[(long long) a[i] * pw[i] % d] += foo[i] + bar[i];
		for (int j = i + 1; j <= n && j < i + 20; ++j) {
			if ((a[j] - (long long) a[i] * base[j - i]) % (d * e) == 0) {
				foo[j] -= bar[i];
				bar[j] += foo[i] + bar[i];
			}
			if (a[j] % e == 0 && (long long) a[i] * pw[i] % d == (long long) a[j] * pw[j] % d) {
				foo[j] += bar[i];
				bar[j] -= foo[i] + bar[i];
			}
		}
	}
	cout << foo[n] + bar[n] << "\n";
}