Count of numbers in range which are divisible by M and have digit D at odd places | Variables to store M , N , D ; Vector to store the digit number in the form of digits ; Dp table to compute the answer ; Function to add the individual digits into the vector ; Iterating through the number and adding the digits into the vector ; Function to subtract 1 from a number represented in a form of a String ; Iterating through the number ; If the first digit is 1 , then make it 0 and add 9 at the end of the String . ; If we need to subtract 1 from 0 , then make it 9 and subtract 1 from the previous digits ; Else , simply subtract 1 ; Function to find the count of numbers in the range [ L , R ] which are divisible by M and have digit D at the odd places ; Base case ; If we have built N - digit number and the number is divisible by m then we have got one possible answer . ; If the answer has already been computed , then return the answer ; The possible digits which we can place at the pos position . ; Iterating through all the digits ; If we have placed all the digits up to pos - 1 equal to their limit and currently we are placing a digit which is smaller than this position 's limit then we can place  0 to 9 at all the next positions  to make the number smaller than R ; Calculating the number upto pos mod m . ; Combinations of numbers as there are 10 digits in the range [ 0 , 9 ] ; Recursively call the function for the next position ; Returning the final answer ; Function to call the function for every query ; Driver code
var m , n , d ; var v = [ ] ; var k = 1000000007 ; var dp = Array ( 2001 ) ; for ( var i = 0 ; i < 2001 ; i ++ ) { dp [ i ] = Array . from ( Array ( 2001 ) , ( ) => Array ( 2 ) ) ; } function init ( l ) { for ( var i = 0 ; i < 2001 ; i ++ ) { for ( var j = 0 ; j < 2001 ; j ++ ) { for ( var k = 0 ; k < 2 ; k ++ ) { dp [ i ] [ j ] [ k ] = - 1 ; } } } v = [ ] ; for ( var i = 0 ; i < l . length ; i ++ ) { v . push ( l [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ) ; } n = l . length ; } function number_minus_one ( a ) { var s = a . substring ( 1 ) ; var s1 = " " ; for ( var i = 0 ; i < s . length - 1 ; i ++ ) s1 += ' ' ; if ( a [ 0 ] == ' ' && s === s1 ) { var l = s . length ; a = a . replace ( a [ 0 ] , ' ' ) ; for ( var i = 0 ; i < l ; i ++ ) a += ' ' ; } else { for ( var i = a . length - 1 ; i >= 0 ; i -- ) { if ( a [ i ] == ' ' ) a = a . replace ( a [ i ] , ' ' ) ; else { a = a . replace ( a [ i ] , String . fromCharCode ( ( ( a [ i ] . charCodeAt ( 0 ) - ' ' . charCodeAt ( 0 ) ) - 1 ) + ' ' . charCodeAt ( 0 ) ) ) ; break ; } } } return a . toString ( ) ; } function fun ( pos , sum , f ) { if ( pos == n ) { if ( sum == 0 ) { return 1 ; } return 0 ; } if ( dp [ pos ] [ sum ] [ f ] != - 1 ) return dp [ pos ] [ sum ] [ f ] ; var lmt = 9 ; if ( f == 0 ) lmt = v [ pos ] ; var ans = 0 ; for ( var i = 0 ; i <= lmt ; i ++ ) { if ( i == d && pos % 2 == 1 ) ans += 0 ; else if ( i != d && pos % 2 == 0 ) ans += 0 ; else { var new_f = f ; if ( f == 0 && i < lmt ) new_f = 1 ; var new_sum = sum ; new_sum *= 10 ; new_sum += i ; new_sum %= m ; ans += fun ( pos + 1 , new_sum , new_f ) ; ans %= k ; } } dp [ pos ] [ sum ] [ f ] = ans ; return dp [ pos ] [ sum ] [ f ] ; } function operations ( L , R ) { init ( R ) ; var ans = fun ( 0 , 0 , 0 ) ; L = number_minus_one ( L ) ; init ( L ) ; ans -= fun ( 0 , 0 , 0 ) ; if ( ans < 0 ) ans += k ; document . write ( ans + " " ) ; } m = 2 ; d = 2 ; var Q = 1 ; var arr = [ [ " " , " " ] ] ; for ( var i = 0 ; i < Q ; i ++ ) { operations ( arr [ i ] [ 0 ] , arr [ i ] [ 1 ] ) ; }