Count the numbers with N digits and whose suffix is divisible by K | Python3 implementation to Count the numbers with N digits and whose suffix is divisible by K ; Suffix of length pos with remainder rem and Z representing whether the suffix has a non zero digit until now ; Base case ; If count of digits is less than n ; Placing all possible digits in remaining positions ; If remainder non zero and suffix has n digits ; If the subproblem is already solved ; Placing all digits at MSB of suffix and increasing it 's length by 1 ; Non zero digit is placed ; Store and return the solution to this subproblem ; Function to Count the numbers with N digits and whose suffix is divisible by K ; Since we need powers of 10 for counting , it 's better to  pre store them along with their  modulo with 1e9 + 7 for counting ; Since at each recursive step we increase the suffix length by 1 by placing digits at its leftmost position , we need powers of 10 modded with k , in order to fpos the new remainder efficiently ; Initialising dp table values - 1 represents subproblem hasn 't  been solved yet  memset(dp, -1, sizeof(dp)) ; Driver Code
mod = 1000000007 NEW_LINE dp = [ [ [ - 1 for i in range ( 2 ) ] for i in range ( 105 ) ] for i in range ( 1005 ) ] NEW_LINE powers = [ 0 ] * 1005 NEW_LINE powersModk = [ 0 ] * 1005 NEW_LINE def calculate ( pos , rem , z , k , n ) : NEW_LINE INDENT if ( rem == 0 and z ) : NEW_LINE INDENT if ( pos != n ) : NEW_LINE INDENT return ( powers [ n - pos - 1 ] * 9 ) % mod NEW_LINE DEDENT else : NEW_LINE INDENT return 1 NEW_LINE DEDENT DEDENT if ( pos == n ) : NEW_LINE INDENT return 0 NEW_LINE DEDENT if ( dp [ pos ] [ rem ] [ z ] != - 1 ) : NEW_LINE INDENT return dp [ pos ] [ rem ] [ z ] NEW_LINE DEDENT count = 0 NEW_LINE for i in range ( 10 ) : NEW_LINE INDENT if ( i == 0 ) : NEW_LINE INDENT count = ( count + ( calculate ( pos + 1 , ( rem + ( i * powersModk [ pos ] ) % k ) % k , z , k , n ) ) ) % mod NEW_LINE DEDENT else : NEW_LINE INDENT count = ( count + ( calculate ( pos + 1 , ( rem + ( i * powersModk [ pos ] ) % k ) % k , 1 , k , n ) ) ) % mod NEW_LINE DEDENT DEDENT dp [ pos ] [ rem ] [ z ] = count NEW_LINE return count NEW_LINE DEDENT def countNumbers ( n , k ) : NEW_LINE INDENT st = 1 NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT powers [ i ] = st NEW_LINE st *= 10 NEW_LINE st %= mod NEW_LINE DEDENT st = 1 NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT powersModk [ i ] = st NEW_LINE st *= 10 NEW_LINE st %= mod NEW_LINE DEDENT return calculate ( 0 , 0 , 0 , k , n ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 2 NEW_LINE K = 2 NEW_LINE print ( countNumbers ( N , K ) ) NEW_LINE DEDENT