#include<bits/stdc++.h>
using namespace std;
#define int long long
#define mod 1000000007
int dp[30001][1002][2];
int countdigitsum(int pos,int d,bool tight,string k,int D){
	int ub = tight? k[pos]-'0': 9;
	if(dp[pos][d][tight]!=-1){
		return dp[pos][d][tight];
	}
	if(pos==k.length()-1){
		int ans=0;
		for(int x=0;x<=ub;x++){
			if(x%D==d){
				ans++;
			}
		}
		return ans;
	}
	int ans=0;
	for(int x=0;x<=ub;x++){
		ans= (ans+countdigitsum(pos+1,(D+d-x%D)%D,tight&&(x==ub),k,D))%mod;
	}
	return dp[pos][d][tight]=ans;
}
signed main(){
	string k;
	cin>>k;
	int D;
	cin>>D;
	memset(dp,-1,sizeof dp);

	cout<<(mod+countdigitsum(0,0,1,k,D)-1)%mod<<endl;
	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>
using namespace std;
#define int long long
#define mod 1000000007
int dp[30001][1002][2];
int countdigitsum(int pos,int d,bool tight,string k,int D){
	int ub = tight? k[pos]-'0': 9;
	if(dp[pos][d][tight]!=-1){
		return dp[pos][d][tight];
	}
	if(pos==k.length()-1){
		int ans=0;
		for(int x=0;x<=ub;x++){
			if(x%D==d){
				ans++;
			}
		}
		return ans;
	}
	int ans=0;
	for(int x=0;x<=ub;x++){
		ans= (ans+countdigitsum(pos+1,(D+d-x%D)%D,tight&&(x==ub),k,D))%mod;
	}
	return dp[pos][d][tight]=ans;
}
signed main(){
	string k;
	cin>>k;
	int D;
	cin>>D;
	memset(dp,-1,sizeof dp);

	cout<<(mod+countdigitsum(0,0,1,k,D)-1)%mod<<endl;
	return 0;
}
```