#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
const int MAXN=100000+100;
const int MOD=1e9+7;
LL dp[MAXN][128],dgt[MAXN];
LL d,len;
string k;

LL dfs(LL pos,LL num,bool lim){
	if(!lim&&dp[pos][num]!=-1) return dp[pos][num];
	if(pos==len+1) return dp[pos][num]=(num==0);
	LL up=lim?dgt[pos]:9;
	LL ret=0;
	for(int i=0;i<=up;i++){
		ret+=dfs(pos+1,(num+i)%d,lim&&(i==up));
		ret%=MOD;
	}
	if(!lim) dp[pos][num]=ret;
	return ret;
}

int main(){
	memset(dp,-1,sizeof(dp));
	cin>>k>>d;
	len=k.size();
	k='$'+k;
	for(int i=1;i<=len;i++) dgt[i]=k[i]-'0';
	LL ans=dfs(1,0,1)-1+MOD;
	cout<<ans%MOD<<endl;
	return 0;
}
 
### Prompt

Your task is to create a cpp solution 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;

typedef long long LL;
const int MAXN=100000+100;
const int MOD=1e9+7;
LL dp[MAXN][128],dgt[MAXN];
LL d,len;
string k;

LL dfs(LL pos,LL num,bool lim){
	if(!lim&&dp[pos][num]!=-1) return dp[pos][num];
	if(pos==len+1) return dp[pos][num]=(num==0);
	LL up=lim?dgt[pos]:9;
	LL ret=0;
	for(int i=0;i<=up;i++){
		ret+=dfs(pos+1,(num+i)%d,lim&&(i==up));
		ret%=MOD;
	}
	if(!lim) dp[pos][num]=ret;
	return ret;
}

int main(){
	memset(dp,-1,sizeof(dp));
	cin>>k>>d;
	len=k.size();
	k='$'+k;
	for(int i=1;i<=len;i++) dgt[i]=k[i]-'0';
	LL ans=dfs(1,0,1)-1+MOD;
	cout<<ans%MOD<<endl;
	return 0;
}
 
```