#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fill(name, val) memset(name, val, sizeof(name));
#define mop(a, op, b)    (a%mod op b%mod)%mod
#define mod 1000000007LL

/*	Author: 🆉🅴🅽🅾🅻🆄🆂	*/

string k;
ll dp[10001][2][101], d;
ll count(ll i, bool tight, ll sum){
	if(i == k.size())	return (sum == 0);
	if(dp[i][tight][sum] != -1)	return dp[i][tight][sum];
	ll ans = 0, high = tight ? k[i]-'0' : 9;
	for(ll j = 0; j <= high; j++)
		ans = mop(ans, +, count(i+1, tight & (j == high), (sum+j)%d));
	return dp[i][tight][sum] = ans;
}
int main(){
	fill(dp, -1);	cin>>k>>d;
	cout<<(count(0, 1, 0) + mod - 1) % mod;
}

// Time: O(D*logK)
// Space: O(D*logK)
### 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;
#define ll long long
#define fill(name, val) memset(name, val, sizeof(name));
#define mop(a, op, b)    (a%mod op b%mod)%mod
#define mod 1000000007LL

/*	Author: 🆉🅴🅽🅾🅻🆄🆂	*/

string k;
ll dp[10001][2][101], d;
ll count(ll i, bool tight, ll sum){
	if(i == k.size())	return (sum == 0);
	if(dp[i][tight][sum] != -1)	return dp[i][tight][sum];
	ll ans = 0, high = tight ? k[i]-'0' : 9;
	for(ll j = 0; j <= high; j++)
		ans = mop(ans, +, count(i+1, tight & (j == high), (sum+j)%d));
	return dp[i][tight][sum] = ans;
}
int main(){
	fill(dp, -1);	cin>>k>>d;
	cout<<(count(0, 1, 0) + mod - 1) % mod;
}

// Time: O(D*logK)
// Space: O(D*logK)
```