#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9+7;

typedef long long ll;

string k;
int n, d;
ll f[2][101][10101]; 

int main()
{
	cin>>k>>d;
	n=k.size();
	f[0][0][0]=1;
	f[1][0][0]=1;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<d;j++)
		{
			f[1][j][i]%=mod;
			f[0][j][i]%=mod;
			for(int b=0;b<=9;b++)
			{
				if(b==(k[n-i-1]-48))	f[1][(j+b)%d][i+1]+=f[1][j][i];	
				if(b<(k[n-i-1]-48))		f[1][(j+b)%d][i+1]+=f[0][j][i];
				f[0][(j+b)%d][i+1]+=f[0][j][i];
			}		
		}
	}
	cout<<((f[1][0][n]-1)+mod)%mod;
}
### 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 mod = 1e9+7;

typedef long long ll;

string k;
int n, d;
ll f[2][101][10101]; 

int main()
{
	cin>>k>>d;
	n=k.size();
	f[0][0][0]=1;
	f[1][0][0]=1;
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<d;j++)
		{
			f[1][j][i]%=mod;
			f[0][j][i]%=mod;
			for(int b=0;b<=9;b++)
			{
				if(b==(k[n-i-1]-48))	f[1][(j+b)%d][i+1]+=f[1][j][i];	
				if(b<(k[n-i-1]-48))		f[1][(j+b)%d][i+1]+=f[0][j][i];
				f[0][(j+b)%d][i+1]+=f[0][j][i];
			}		
		}
	}
	cout<<((f[1][0][n]-1)+mod)%mod;
}
```