#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
int a[10002], n, d; ll dp[10002][102][2]; string s;
ll solve(int pos, int sum, bool lmt){
    if(pos == n) return sum == 0;
    if(dp[pos][sum][lmt] != -1) return dp[pos][sum][lmt];
    int hi = lmt? a[pos]: 9; ll ret = 0;
    for(int i=0; i<=hi; i++){
        ret += solve(pos+1, (sum+i)%d, lmt && (i==a[pos])); 
    }
    return dp[pos][sum][lmt] = ret % mod;
}
int main(){
    memset(dp, -1, sizeof(dp));
    cin >> s >> d; n = s.size();
    for(int i=0; i<n; i++) a[i] = s[i] - '0';
    cout << ( solve(0, 0, 1) - 1 + mod) % mod << endl;
}
### 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;
typedef long long ll;
const int mod = 1e9+7;
int a[10002], n, d; ll dp[10002][102][2]; string s;
ll solve(int pos, int sum, bool lmt){
    if(pos == n) return sum == 0;
    if(dp[pos][sum][lmt] != -1) return dp[pos][sum][lmt];
    int hi = lmt? a[pos]: 9; ll ret = 0;
    for(int i=0; i<=hi; i++){
        ret += solve(pos+1, (sum+i)%d, lmt && (i==a[pos])); 
    }
    return dp[pos][sum][lmt] = ret % mod;
}
int main(){
    memset(dp, -1, sizeof(dp));
    cin >> s >> d; n = s.size();
    for(int i=0; i<n; i++) a[i] = s[i] - '0';
    cout << ( solve(0, 0, 1) - 1 + mod) % mod << endl;
}
```