#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll d,mod = 1000000007;
ll dp[10009][109][9];
string s;
ll bt(ll id,ll sum,ll t){
	if(id == s.size()) return (sum%d==0);
	ll &ret = dp[id][sum][t];
	if(ret != -1) return ret;
	ret = 0;
	if(t == 1){
		for(int i=0;i<=9;i++){
			ret = (ret + bt(id+1,(sum+i)%d,1)) % mod;
		}
	}
	else{
		ll n = s[id] - '0';
		for(int i=0;i<n;i++){
			ret = (ret + bt(id+1,(sum+i)%d,1)) % mod;
		}
		ret = (ret + bt(id+1,(sum+n)%d,0)) % mod;
	}
	return ret;
}
int main(){
	cin>>s>>d;
	memset(dp,-1,sizeof(dp));
	cout<<(bt(0,0,0)+mod-1)%mod<<endl;
}

### Prompt

Develop a solution in Cpp to the problem described below:

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 ll long long
using namespace std;
ll d,mod = 1000000007;
ll dp[10009][109][9];
string s;
ll bt(ll id,ll sum,ll t){
	if(id == s.size()) return (sum%d==0);
	ll &ret = dp[id][sum][t];
	if(ret != -1) return ret;
	ret = 0;
	if(t == 1){
		for(int i=0;i<=9;i++){
			ret = (ret + bt(id+1,(sum+i)%d,1)) % mod;
		}
	}
	else{
		ll n = s[id] - '0';
		for(int i=0;i<n;i++){
			ret = (ret + bt(id+1,(sum+i)%d,1)) % mod;
		}
		ret = (ret + bt(id+1,(sum+n)%d,0)) % mod;
	}
	return ret;
}
int main(){
	cin>>s>>d;
	memset(dp,-1,sizeof(dp));
	cout<<(bt(0,0,0)+mod-1)%mod<<endl;
}

```