#include <bits/stdc++.h>

using namespace std;

const int mod = 1e9 + 7;
int ans;
int dp[10002][102][2];
char s[10002];
int d;

int main()
{
  cin >> (s + 1);
  cin >> d;
  int n = strlen(s + 1);
  reverse(s + 1,s + n + 1);
  dp[0][0][1] = 1;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < d; j++)
      for (int leq = 1; leq >= 0; leq--)
        for (int cif = 0; cif < 10; cif++) {
          int nextleq = (cif < s[i + 1] - '0' || (cif == s[i + 1] - '0' && leq));
          dp[i + 1][(j + cif) % d][nextleq] += dp[i][j][leq];
          dp[i + 1][(j + cif) % d][nextleq] %= mod;
        }
  cout << (dp[n][0][1] - 1 + mod) % mod;
  return 0;
}

### Prompt

Please create a solution in Cpp 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>

using namespace std;

const int mod = 1e9 + 7;
int ans;
int dp[10002][102][2];
char s[10002];
int d;

int main()
{
  cin >> (s + 1);
  cin >> d;
  int n = strlen(s + 1);
  reverse(s + 1,s + n + 1);
  dp[0][0][1] = 1;
  for (int i = 0; i < n; i++)
    for (int j = 0; j < d; j++)
      for (int leq = 1; leq >= 0; leq--)
        for (int cif = 0; cif < 10; cif++) {
          int nextleq = (cif < s[i + 1] - '0' || (cif == s[i + 1] - '0' && leq));
          dp[i + 1][(j + cif) % d][nextleq] += dp[i][j][leq];
          dp[i + 1][(j + cif) % d][nextleq] %= mod;
        }
  cout << (dp[n][0][1] - 1 + mod) % mod;
  return 0;
}

```