#include using namespace std; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FORR(x,arr) for(auto&& x:arr) #define FOR(i,a,b) for (int i = (a); i < (b); i++) #define RFOR(i,a,b) for (int i = (b)-1; i >= (a); i--) #define REP(i,n) for (int i = 0; i < (n); i++) #define RREP(i,n) for (int i = (n)-1; i >= 0; i--) #define ALL(x) (x).begin(), (x).end() #define BIT(n) (1LL<<(n)) #define SZ(x) ((int)(x).size()) typedef long long ll; // ------------------------------------- const long long mod = 1000000007; string S; int M; int N; int dp[2][20000]; long long powMod(long long x, long long y) { long long r = 1, a = x % M; while (y) { if (y & 1) r = (r * a) % M; a = (a * a) % M; y /= 2; } return r; } void Main() { cin >> S >> M; N = SZ(S); dp[0][0] = 1; int zc = 0; REP(i, N) { int x = i % 2; int y = (i + 1) % 2; REP(i, M) dp[y][i] = dp[x][i]; int d = S[i] - '0'; //_P("%d\n", d); //REP(z, M) _P("dp[%d][%d]: %d\n", x, z, dp[x][z]); REP(j, M) { int a = (j * 10 + d) % M; (dp[y][a] += dp[x][j]) %= mod; } if (d == 0) { zc++; dp[y][0]--; } //REP(z, M) _P("dp[%d][%d]: %d\n", y, z, dp[y][z]); } _P("%lld\n", (dp[N % 2][0] - 1 + zc + mod) % mod); } int main() { cin.tie(0); ios::sync_with_stdio(false); Main(); return 0; }