#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define db(...) #__VA_ARGS__ << ": " << __VA_ARGS__
using ii=long long;
const int M = 1e9 + 7;
string s;
int MOD;
int pd[1 << 15][2][101];
ii dp[1 << 15][2][101];
ii calc(int x, int f, int m)
{
    if (x == s.size()) return m == 0;
    if (pd[x][f][m]) return dp[x][f][m];
    pd[x][f][m] = 1;
    ii r = 0;
    for (int j = 0; j <= (f ? 9 : s[x]); ++j) {
        r += calc(x + 1, f || (j < s[x]), (m + j) % MOD);
        r %= M;
    }
    return dp[x][f][m] = r;
}
int main()
{
    cin >> s >> MOD;
    for (char &c : s) c -= '0';
    cout << (calc(0, 0, 0) - 1 + M) % M << "\n";;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

Find the number of integers between 1 and K (inclusive) satisfying the following condition, modulo 10^9 + 7:

* The sum of the digits in base ten is a multiple of D.

Constraints

* All values in input are integers.
* 1 \leq K < 10^{10000}
* 1 \leq D \leq 100

Input

Input is given from Standard Input in the following format:


K
D


Output

Print the number of integers satisfying the condition, modulo 10^9 + 7.

Examples

Input

30
4


Output

6


Input

1000000009
1


Output

2


Input

98765432109876543210
58


Output

635270834

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(),x.end()
#define db(...) #__VA_ARGS__ << ": " << __VA_ARGS__
using ii=long long;
const int M = 1e9 + 7;
string s;
int MOD;
int pd[1 << 15][2][101];
ii dp[1 << 15][2][101];
ii calc(int x, int f, int m)
{
    if (x == s.size()) return m == 0;
    if (pd[x][f][m]) return dp[x][f][m];
    pd[x][f][m] = 1;
    ii r = 0;
    for (int j = 0; j <= (f ? 9 : s[x]); ++j) {
        r += calc(x + 1, f || (j < s[x]), (m + j) % MOD);
        r %= M;
    }
    return dp[x][f][m] = r;
}
int main()
{
    cin >> s >> MOD;
    for (char &c : s) c -= '0';
    cout << (calc(0, 0, 0) - 1 + M) % M << "\n";;
}

```