Sum of Digits of the Good Strings | C # 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
using System ; class GFG { readonly static int DIGITS = 10 ; readonly static int MAX = 10000 ; readonly static int MOD = 1000000007 ; static int [ , ] dp = new int [ MAX , DIGITS ] ; static int [ , ] cnt = new int [ MAX , DIGITS ] ; static void precompute ( ) { for ( int i = 0 ; i < DIGITS ; i ++ ) { dp [ 1 , i ] = i ; cnt [ 1 , i ] = 1 ; } for ( int i = 2 ; i < MAX ; i ++ ) { for ( int j = 0 ; j < DIGITS ; j ++ ) { for ( int 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 ; } } } } } public static void Main ( String [ ] args ) { int x = 6 , y = 4 ; precompute ( ) ; Console . WriteLine ( dp [ x , y ] ) ; } }