#include <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
#define REP(i,n) for (int i = 0; i < n; ++i)
#define FOR(i,m,n) for (int i = m; i < n; ++i)

const int MAX_K = 1e4+11;
const int MAX_D = 120;
const int MOD = 1e9+7;
string K;
int D;
ll dp[MAX_K][MAX_D];

int main () {
	cin >> K >> D;
    int l = K.size();
	dp[0][0] = 1;
    FOR (i, 1, MAX_K) REP (j, D) REP (k, 10)
	    (dp[i][j] += dp[i-1][(j-k+10*D)%D]) %= MOD;
	
    ll ans = 0;
	ll s = 0;
    REP (i, l) {
		int k = K[i] - '0';
        FOR (j, 1, k+1) {
			int t = (D*D*D-(s+j-1))%D;
			(ans += dp[l-1-i][t]) %= MOD;	
		}	
		(s += k) %= D;
	}
	if (s%D) (ans += MOD - 1) %= MOD;
	cout << ans << 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 <iostream>
#include <algorithm>

using namespace std;
typedef long long ll;
#define REP(i,n) for (int i = 0; i < n; ++i)
#define FOR(i,m,n) for (int i = m; i < n; ++i)

const int MAX_K = 1e4+11;
const int MAX_D = 120;
const int MOD = 1e9+7;
string K;
int D;
ll dp[MAX_K][MAX_D];

int main () {
	cin >> K >> D;
    int l = K.size();
	dp[0][0] = 1;
    FOR (i, 1, MAX_K) REP (j, D) REP (k, 10)
	    (dp[i][j] += dp[i-1][(j-k+10*D)%D]) %= MOD;
	
    ll ans = 0;
	ll s = 0;
    REP (i, l) {
		int k = K[i] - '0';
        FOR (j, 1, k+1) {
			int t = (D*D*D-(s+j-1))%D;
			(ans += dp[l-1-i][t]) %= MOD;	
		}	
		(s += k) %= D;
	}
	if (s%D) (ans += MOD - 1) %= MOD;
	cout << ans << endl;
}
```