#include <bits/stdc++.h>
using namespace std;

const int N=1e4+5,zqm=1e9+7;
int f[N][100],n,d;
char num[N];

int dp(int x,int y,bool ub) {
	int lim=(ub ? num[x] : 9);
	if(x==n) return lim/d+1-(lim/d*d+y>lim);
	if(!ub&&f[x][y]!=-1) return f[x][y];
	int ret=0;
	for(int i=lim;i>=0;--i) {
		(ret+=dp(x+1,(y-i+d)%d,ub&&i==num[x]))%=zqm;
	}
	if(!ub) f[x][y]=ret;
	//cerr<<x<<' '<<y<<' '<<ub<<' '<<ret<<endl;
	return ret;
}

int main() {
	//freopen("1.in","r",stdin);
	//freopen("1.ans","w",stdout);
	
	scanf("%s%d",num+1,&d);
	n=strlen(num+1);
	for(int i=1;i<=n;++i) num[i]-=48;
	memset(f,255,sizeof(f));
	printf("%d\n",(dp(1,0,1)+zqm-1)%zqm);
	
	return 0;
}

### Prompt

Generate 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;

const int N=1e4+5,zqm=1e9+7;
int f[N][100],n,d;
char num[N];

int dp(int x,int y,bool ub) {
	int lim=(ub ? num[x] : 9);
	if(x==n) return lim/d+1-(lim/d*d+y>lim);
	if(!ub&&f[x][y]!=-1) return f[x][y];
	int ret=0;
	for(int i=lim;i>=0;--i) {
		(ret+=dp(x+1,(y-i+d)%d,ub&&i==num[x]))%=zqm;
	}
	if(!ub) f[x][y]=ret;
	//cerr<<x<<' '<<y<<' '<<ub<<' '<<ret<<endl;
	return ret;
}

int main() {
	//freopen("1.in","r",stdin);
	//freopen("1.ans","w",stdout);
	
	scanf("%s%d",num+1,&d);
	n=strlen(num+1);
	for(int i=1;i<=n;++i) num[i]-=48;
	memset(f,255,sizeof(f));
	printf("%d\n",(dp(1,0,1)+zqm-1)%zqm);
	
	return 0;
}

```