#include<bits/stdc++.h>
using namespace std;

const int MXN=10005;
const int MOD=1e9+7;
int add(int&x,int y){return(x+=y)<MOD?x:x-=MOD;}
int sub(int&x,int y){return(x-=y)>= 0?x:x+=MOD;}

char K[MXN];
int D,dp[MXN][105][2];

int main(){
  dp[0][0][0]=1;
  dp[0][0][1]=1;
  scanf("%s%d",K,&D);
  int N=strlen(K);
  reverse(K,K+N);
  for(int i=0;K[i];++i){
    for(int d=0;d<=9;++d){
      for(int k=0;k<D;++k){
        add(dp[i+1][(k+d)%D][0],dp[i][k][0]);
        if(d+'0'<K[i])
        add(dp[i+1][(k+d)%D][1],dp[i][k][0]);
        if(d+'0'==K[i])
        add(dp[i+1][(k+d)%D][1],dp[i][k][1]);
      }
    }
  }
  printf("%d\n",sub(dp[N][0][1],1));
}

### Prompt

Develop a solution in cpp 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>
using namespace std;

const int MXN=10005;
const int MOD=1e9+7;
int add(int&x,int y){return(x+=y)<MOD?x:x-=MOD;}
int sub(int&x,int y){return(x-=y)>= 0?x:x+=MOD;}

char K[MXN];
int D,dp[MXN][105][2];

int main(){
  dp[0][0][0]=1;
  dp[0][0][1]=1;
  scanf("%s%d",K,&D);
  int N=strlen(K);
  reverse(K,K+N);
  for(int i=0;K[i];++i){
    for(int d=0;d<=9;++d){
      for(int k=0;k<D;++k){
        add(dp[i+1][(k+d)%D][0],dp[i][k][0]);
        if(d+'0'<K[i])
        add(dp[i+1][(k+d)%D][1],dp[i][k][0]);
        if(d+'0'==K[i])
        add(dp[i+1][(k+d)%D][1],dp[i][k][1]);
      }
    }
  }
  printf("%d\n",sub(dp[N][0][1],1));
}

```