#include <bits/stdc++.h>
using namespace std;

string s;
int D;
long long dp[10010][110][2] , mod = 1e9 + 7;

long long get(int i = 0 , int sum = 0 , bool flag = 0)
{
    if(i == s.size())return (sum == 0);
    long long &ret = dp[i][sum][flag];
    if(~ret)    return ret;

    ret = 0;
    for(int j = 0 ; j <= (flag ? 9 : s[i] - '0') ; j++)
        ret = (ret + get(i+1,(sum + j)%D, flag | (j < s[i] - '0')))%mod;

    return ret;
}
int main()
{
    cin.tie();  ios::sync_with_stdio(false);
    cin >> s >> D;
    memset(dp,-1,sizeof dp);
    cout << (get() +mod - 1)%mod<< '\n';
    return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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;

string s;
int D;
long long dp[10010][110][2] , mod = 1e9 + 7;

long long get(int i = 0 , int sum = 0 , bool flag = 0)
{
    if(i == s.size())return (sum == 0);
    long long &ret = dp[i][sum][flag];
    if(~ret)    return ret;

    ret = 0;
    for(int j = 0 ; j <= (flag ? 9 : s[i] - '0') ; j++)
        ret = (ret + get(i+1,(sum + j)%D, flag | (j < s[i] - '0')))%mod;

    return ret;
}
int main()
{
    cin.tie();  ios::sync_with_stdio(false);
    cin >> s >> D;
    memset(dp,-1,sizeof dp);
    cout << (get() +mod - 1)%mod<< '\n';
    return 0;
}

```