#include<bits/stdc++.h>
using namespace std;
const int N=1e4+10,MOD=1e9+7;
char a[N];
int n,D,num[N],dp[N][110];
int Search(int k,int sum,int lim,int preo)
{
	if ((!lim)&&(!preo)&&dp[k][sum]!=-1) return dp[k][sum];//´íÎó±Ê¼Ç£º¶¨¸ñºÍÓÐÇ°µ¼0µÄÇé¿ö²»ÄÜÖ±½Ó·µ»Ø 
	if (k>n) if (!sum) return 1; else return 0;
	int s=0,maxd=(lim?num[k]:9);
	for (register int i=0;i<=maxd;++i) s=(s+Search(k+1,(sum+i)%D,lim&&(i==num[k]),preo&&(i==0)))%MOD;
	if ((!lim)&&(!preo)) dp[k][sum]=s;
	return s;
}
int main()
{
	scanf("%s%d",a+1,&D);n=strlen(a+1);
	for (register int i=1;i<=n;++i) num[i]=a[i]-'0';
	memset(dp,-1,sizeof(dp));
	printf("%d\n",(Search(1,0,1,1)-1+MOD)%MOD);
	return 0;
}
### 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;
const int N=1e4+10,MOD=1e9+7;
char a[N];
int n,D,num[N],dp[N][110];
int Search(int k,int sum,int lim,int preo)
{
	if ((!lim)&&(!preo)&&dp[k][sum]!=-1) return dp[k][sum];//´íÎó±Ê¼Ç£º¶¨¸ñºÍÓÐÇ°µ¼0µÄÇé¿ö²»ÄÜÖ±½Ó·µ»Ø 
	if (k>n) if (!sum) return 1; else return 0;
	int s=0,maxd=(lim?num[k]:9);
	for (register int i=0;i<=maxd;++i) s=(s+Search(k+1,(sum+i)%D,lim&&(i==num[k]),preo&&(i==0)))%MOD;
	if ((!lim)&&(!preo)) dp[k][sum]=s;
	return s;
}
int main()
{
	scanf("%s%d",a+1,&D);n=strlen(a+1);
	for (register int i=1;i<=n;++i) num[i]=a[i]-'0';
	memset(dp,-1,sizeof(dp));
	printf("%d\n",(Search(1,0,1,1)-1+MOD)%MOD);
	return 0;
}
```