Sum of Digits of the Good Strings | Javascript implementation of the approach ; To store the states of the dp ; Function to fill the dp table ; Sum of digits of the string of length 1 is i as i is only number in that string and count of good strings of length 1 that end with i is also 1 ; Adjacent digits are different ; Increment the count as digit at ( i - 1 ) 'th index is k and count  of good strings is equal to this  because at the end of the strings of  length (i - 1) we are just  putting digit j as the last digit ; Driver code
var DIGITS = 10 var MAX = 10000 var MOD = 1000000007 var dp = Array . from ( Array ( MAX ) , ( ) => Array ( DIGITS ) . fill ( 0 ) ) ; var cnt = Array . from ( Array ( MAX ) , ( ) => Array ( DIGITS ) . fill ( 0 ) ) ; function precompute ( ) { for ( var i = 0 ; i < DIGITS ; i ++ ) dp [ 1 ] [ i ] = i , cnt [ 1 ] [ i ] = 1 ; for ( var i = 2 ; i < MAX ; i ++ ) { for ( var j = 0 ; j < DIGITS ; j ++ ) { for ( var k = 0 ; k < DIGITS ; k ++ ) { if ( j != k ) { dp [ i ] [ j ] = dp [ i ] [ j ] + ( dp [ i - 1 ] [ k ] + ( cnt [ i - 1 ] [ k ] * j ) % MOD ) % MOD ; dp [ i ] [ j ] %= MOD ; cnt [ i ] [ j ] += cnt [ i - 1 ] [ k ] ; cnt [ i ] [ j ] %= MOD ; } } } } } var x = 6 , y = 4 ; precompute ( ) ; document . write ( dp [ x ] [ y ] ) ;