#include <bits/stdc++.h>
const int INF=1e9,MOD=1e9+7;
const long long LINF=1e18;
using namespace std;
#define int long long
//template
int dp[12345][123];
//main
signed main(){
  string s;int D;cin>>s>>D;
  int sum=0;
  memset(dp,0,sizeof(dp));
  for(int i=0;i<s.size();i++){
    for(int j=0;j<D;j++){
      for(int k=0;k<10;k++){dp[i+1][(j+k)%D]+=dp[i][j];dp[i+1][(j+k)%D]%=MOD;}
    }
    for(int k=0;k<s[i]-'0';k++){dp[i+1][(sum+k)%D]++;dp[i+1][(sum+k)%D]%=MOD;}
    sum+=s[i]-'0';
    sum%=MOD;
  }
  int a=0;
  for(char p:s)a+=p-'0';a%=D;
  if(a==0)cout<<dp[s.size()][0]<<endl;
  else cout<<(dp[s.size()][0]-1+MOD)%MOD<<endl;
}

### Prompt

Your task is to create 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>
const int INF=1e9,MOD=1e9+7;
const long long LINF=1e18;
using namespace std;
#define int long long
//template
int dp[12345][123];
//main
signed main(){
  string s;int D;cin>>s>>D;
  int sum=0;
  memset(dp,0,sizeof(dp));
  for(int i=0;i<s.size();i++){
    for(int j=0;j<D;j++){
      for(int k=0;k<10;k++){dp[i+1][(j+k)%D]+=dp[i][j];dp[i+1][(j+k)%D]%=MOD;}
    }
    for(int k=0;k<s[i]-'0';k++){dp[i+1][(sum+k)%D]++;dp[i+1][(sum+k)%D]%=MOD;}
    sum+=s[i]-'0';
    sum%=MOD;
  }
  int a=0;
  for(char p:s)a+=p-'0';a%=D;
  if(a==0)cout<<dp[s.size()][0]<<endl;
  else cout<<(dp[s.size()][0]-1+MOD)%MOD<<endl;
}

```