#include <bits/stdc++.h>
#define MOD ((int)(1e9+7))

using namespace std;

string s;
int d;
int mem[10004][105][2];

int go(int ind,int r,int l)
{
	//cout << ind << " " << r << " " <<l << endl;
	if(ind>=s.size()) return r==0;
	if(mem[ind][r][l]!=-1) return mem[ind][r][l];
	mem[ind][r][l]=0;
	for(int i='0';i<=(l?'9':s[ind]);i++)
	{
		mem[ind][r][l]+=go(ind+1,(r+(i-'0'))%d,(i<s[ind])|l);
		mem[ind][r][l]%=MOD;
	}
	return mem[ind][r][l];
}

int main()
{
	cin >> s >> d;
	memset(mem,-1,sizeof mem);
	cout << (go(0,0,0)+MOD-1)%MOD << endl;
}
### 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>
#define MOD ((int)(1e9+7))

using namespace std;

string s;
int d;
int mem[10004][105][2];

int go(int ind,int r,int l)
{
	//cout << ind << " " << r << " " <<l << endl;
	if(ind>=s.size()) return r==0;
	if(mem[ind][r][l]!=-1) return mem[ind][r][l];
	mem[ind][r][l]=0;
	for(int i='0';i<=(l?'9':s[ind]);i++)
	{
		mem[ind][r][l]+=go(ind+1,(r+(i-'0'))%d,(i<s[ind])|l);
		mem[ind][r][l]%=MOD;
	}
	return mem[ind][r][l];
}

int main()
{
	cin >> s >> d;
	memset(mem,-1,sizeof mem);
	cout << (go(0,0,0)+MOD-1)%MOD << endl;
}
```