#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#define rep(i, n)   for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

const ll mod = 1e9+7;

int main(){
    string K;   cin>>K;
    int d;  cin>>d;
    int n = K.size();
    vector<vector<vector<ll>>>dp(n+1, vector<vector<ll>>(2, vector<ll>(d)));
    dp[0][0][0] = 1;
    rep(i, n)   rep(j, 2)   rep(k, d){
        int l = j?9:K[i]-'0';
        rep(x, l+1){
            (dp[i+1][j || x < l][(k+x)%d] += dp[i][j][k]) %= mod;
        }
    }
    ll ans = 0;
    rep(j, 2)   (ans += dp[n][j][0]) %= mod;
    cout << (ans+mod-1)%mod << endl;
}

### Prompt

Your challenge is to write 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 <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <set>
#include <map>
#define rep(i, n)   for(int i = 0; i < (n); i++)
using namespace std;
typedef long long ll;

const ll mod = 1e9+7;

int main(){
    string K;   cin>>K;
    int d;  cin>>d;
    int n = K.size();
    vector<vector<vector<ll>>>dp(n+1, vector<vector<ll>>(2, vector<ll>(d)));
    dp[0][0][0] = 1;
    rep(i, n)   rep(j, 2)   rep(k, d){
        int l = j?9:K[i]-'0';
        rep(x, l+1){
            (dp[i+1][j || x < l][(k+x)%d] += dp[i][j][k]) %= mod;
        }
    }
    ll ans = 0;
    rep(j, 2)   (ans += dp[n][j][0]) %= mod;
    cout << (ans+mod-1)%mod << endl;
}

```