#include <bits/stdc++.h>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

const int MOD = 1e9 + 7;
ll dp[10005][2][100];

int main(){
	
	string s;
	cin >> s;
	int d;
	cin >> d;
	
	// 1桁目
	int first = s[0] - '0';
	rep(i,first+1) dp[0][i < first][i%d]++;
	
	// 2桁目以降
	rep(i,s.size()-1) rep(j,2) rep(k,d){
		int lim = j? 9 : s[i+1] - '0';
		rep(next, lim+1){
			dp[i+1][j || next < lim][(k + next) % d] = (dp[i+1][j || next < lim][(k + next) % d] + dp[i][j][k]) % MOD;
		}
	}
	
	ll res = 0;
	rep(j,2) res = (res + dp[s.size()-1][j][0]) % MOD;
	
	cout << (res -1 + MOD) % MOD << endl; // 0を含んでいる為1減算
	
	return 0;
}
### Prompt

Please create a solution in Cpp 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>
#define rep(i,n) for (int i = 0; i < (n); ++i)
using namespace std;
typedef long long ll;

const int MOD = 1e9 + 7;
ll dp[10005][2][100];

int main(){
	
	string s;
	cin >> s;
	int d;
	cin >> d;
	
	// 1桁目
	int first = s[0] - '0';
	rep(i,first+1) dp[0][i < first][i%d]++;
	
	// 2桁目以降
	rep(i,s.size()-1) rep(j,2) rep(k,d){
		int lim = j? 9 : s[i+1] - '0';
		rep(next, lim+1){
			dp[i+1][j || next < lim][(k + next) % d] = (dp[i+1][j || next < lim][(k + next) % d] + dp[i][j][k]) % MOD;
		}
	}
	
	ll res = 0;
	rep(j,2) res = (res + dp[s.size()-1][j][0]) % MOD;
	
	cout << (res -1 + MOD) % MOD << endl; // 0を含んでいる為1減算
	
	return 0;
}
```