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

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

```