#include #include #include #include #include #include #include #include #include #include static const int MOD = 1000000007; using ll = long long; using u32 = uint32_t; using namespace std; template constexpr T INF = ::numeric_limits::max() / 32 * 15 + 208; template ostream& operator<<(ostream& os, vector v) { os << "{"; for (int i = 0; i < v.size(); ++i) { if(i) os << ", "; os << v[i]; } return os << "}"; } template ostream& operator<<(ostream& os, pair p) { return os << "{" << p.first << ", " << p.second << "}"; } int main() { string s; int n, m; cin >> s >> m; n = s.size(); vector> dp(2, vector(m)); dp[0][0] = 1; int a = 0; int x = 10%m; for (int i = 0; i < n; ++i) { int now = i&1, nxt = now^1; copy(dp[now].begin(),dp[now].end(), dp[nxt].begin()); int to = (s[i]-'0')%m; if(s[i] == '0') { dp[nxt][0] = (dp[nxt][0] == 0 ? MOD-1 : dp[nxt][0]-1); a++; } for (int j = 0; j < m; ++j, to += x) { while (to >= m) to -= m; dp[nxt][to] += dp[now][j]; if(dp[nxt][to] >= MOD) dp[nxt][to] -= MOD; } } cout << (dp[n&1][0]+a+MOD-1)%MOD << "\n"; return 0; }