#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll M = 1e9+7;

ll bd[10000][100], d;
string s;

int main() {
	getline(cin, s);
	cin >> d;
	memset(bd, 0, sizeof(bd));
	bd[0][0] = 1;
	for (int i=1; i<s.length(); i++) {
		for (int j=0; j<10; j++) {
			bd[i][0] += bd[i-1][(10*d-j)%d];
			bd[i][0] %= M;
		}
		for (int j=1; j<d; j++) {
			bd[i][j] = bd[i][j-1]+bd[i-1][j]-bd[i-1][(j-10+10*d)%d]+M;
			bd[i][j] %= M;
		}
	}
	ll cnt = 0;
	ll sum = 0;
	for (int i=0; i<s.length(); i++) {
		for (int j=0; j<s[i]-'0'; j++) {
			cnt += bd[s.length()-1-i][((-sum-j)%d+d)%d];
			cnt %= M;
		}
		sum += s[i]-'0';
	}
	cnt += bd[0][sum%d];
	cout << (cnt-1+M)%M << "\n";
}
### Prompt

In CPP, your task is to solve 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 ll M = 1e9+7;

ll bd[10000][100], d;
string s;

int main() {
	getline(cin, s);
	cin >> d;
	memset(bd, 0, sizeof(bd));
	bd[0][0] = 1;
	for (int i=1; i<s.length(); i++) {
		for (int j=0; j<10; j++) {
			bd[i][0] += bd[i-1][(10*d-j)%d];
			bd[i][0] %= M;
		}
		for (int j=1; j<d; j++) {
			bd[i][j] = bd[i][j-1]+bd[i-1][j]-bd[i-1][(j-10+10*d)%d]+M;
			bd[i][j] %= M;
		}
	}
	ll cnt = 0;
	ll sum = 0;
	for (int i=0; i<s.length(); i++) {
		for (int j=0; j<s[i]-'0'; j++) {
			cnt += bd[s.length()-1-i][((-sum-j)%d+d)%d];
			cnt %= M;
		}
		sum += s[i]-'0';
	}
	cnt += bd[0][sum%d];
	cout << (cnt-1+M)%M << "\n";
}
```