#include<cstdio>
#include<cstring>
#include<algorithm>
#define qmax(x,y) (x=max(x,y));
using namespace std;

typedef long long ll;
const int Maxn=11000;
const ll mod=1000000007;

char a[Maxn];
int k,f[Maxn][110],ans;

int main() {
	scanf("%s",a);
	scanf("%d",&k);
	int n=strlen(a);
	f[0][0]=1;
	for(int i=1;i<n;i++)
		for(int l=0;l<=9;l++)
		for(int j=0;j<=k;j++) f[i][(j+l)%k]=(f[i][(j+l)%k]+f[i-1][j])%mod;
	int sum=0;
	for(int i=0;i<n;sum=(sum+a[i]-'0')%k,i++)
		for(int j=0;j<a[i]-'0';j++) {
			ans+=f[n-i-1][(k-(sum+j)%k)%k];
			ans%=mod;
		}
	if(sum==0) ans++;ans--;ans+=mod;
	ans%=mod;
	printf("%d",ans);
	return 0;
}

### Prompt

Please provide a CPP coded solution to the problem described below:

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<cstdio>
#include<cstring>
#include<algorithm>
#define qmax(x,y) (x=max(x,y));
using namespace std;

typedef long long ll;
const int Maxn=11000;
const ll mod=1000000007;

char a[Maxn];
int k,f[Maxn][110],ans;

int main() {
	scanf("%s",a);
	scanf("%d",&k);
	int n=strlen(a);
	f[0][0]=1;
	for(int i=1;i<n;i++)
		for(int l=0;l<=9;l++)
		for(int j=0;j<=k;j++) f[i][(j+l)%k]=(f[i][(j+l)%k]+f[i-1][j])%mod;
	int sum=0;
	for(int i=0;i<n;sum=(sum+a[i]-'0')%k,i++)
		for(int j=0;j<a[i]-'0';j++) {
			ans+=f[n-i-1][(k-(sum+j)%k)%k];
			ans%=mod;
		}
	if(sum==0) ans++;ans--;ans+=mod;
	ans%=mod;
	printf("%d",ans);
	return 0;
}

```