#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll Mod = 1e9 + 7;
const ll N = 10100;

ll Rec(ll i=0,ll m=0,bool Equal=true);

string k;
ll n;
ll D;
ll s[N];

ll Dp[N][110][2];

int main()
{
    memset(Dp,-1,sizeof(Dp));

    cin>>k>>D;

    n = k.size();

    for(ll i=0;i<n;i++) s[i] = k[i] - '0';

    cout<<(Rec()-1+Mod)%Mod;
}

ll Rec(ll i,ll m,bool Equal)
{
    if(i==n)    return m==0;

    if(Dp[i][m][Equal]+1)   return Dp[i][m][Equal];

    ll Res = 0;

    for(ll j = 0 , L = Equal ? s[i] : 9 ; j<=L ; j++ )  Res += Rec(i+1,(m+j)%D,Equal&&s[i]==j);

    return Dp[i][m][Equal] = Res%Mod;
}
### 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 <bits/stdc++.h>
#define ll long long

using namespace std;

const ll Mod = 1e9 + 7;
const ll N = 10100;

ll Rec(ll i=0,ll m=0,bool Equal=true);

string k;
ll n;
ll D;
ll s[N];

ll Dp[N][110][2];

int main()
{
    memset(Dp,-1,sizeof(Dp));

    cin>>k>>D;

    n = k.size();

    for(ll i=0;i<n;i++) s[i] = k[i] - '0';

    cout<<(Rec()-1+Mod)%Mod;
}

ll Rec(ll i,ll m,bool Equal)
{
    if(i==n)    return m==0;

    if(Dp[i][m][Equal]+1)   return Dp[i][m][Equal];

    ll Res = 0;

    for(ll j = 0 , L = Equal ? s[i] : 9 ; j<=L ; j++ )  Res += Rec(i+1,(m+j)%D,Equal&&s[i]==j);

    return Dp[i][m][Equal] = Res%Mod;
}
```