| 4 | int mod = 1e9+7; |
| 5 | int dp[2001][2001][2]; |
| 6 | int func(string&v,int i,int cond,int d,int m,int rem) { |
| 7 | |
| 8 | if(i==v.size()) { |
| 9 | |
| 10 | return rem==0; |
| 11 | } else { |
| 12 | if(dp[i][rem][cond]!=-1) return dp[i][rem][cond]; |
| 13 | int last; |
| 14 | if(cond) last=9; |
| 15 | else last = v[i]-'0'; |
| 16 | int ans=0; |
| 17 | for(int j=0;j<=last;j++) { |
| 18 | int newCond=cond; |
| 19 | if(j<last)newCond=1; |
| 20 | if((j==d&&(i%2))||(j!=d&&(i%2==0))) { |
| 21 | |
| 22 | ans+=func(v,i+1,newCond,d,m,((rem*10)%m+j)%m); |
| 23 | ans%=mod; |
| 24 | |
| 25 | } |
| 26 | |
| 27 | } |
| 28 | return dp[i][rem][cond]=ans; |
| 29 | } |
| 30 | } |
| 31 | |
| 32 | int32_t main() { |
| 33 | int d,m; |