Calculate total count of sequences of length even_count with sum divisible by A where first digit can be zero
long [ , ] dp = new long [ even_count , max_sum + 1 ] ; for ( int i = 0 ; i <= 9 ; i ++ ) dp [ 0 , i % A ] ++ ; for ( int i = 1 ; i < even_count ; i ++ ) { for ( int j = 0 ; j <= 9 ; j ++ ) { for ( int k = 0 ; k <= max_sum ; k ++ ) { if ( dp [ i - 1 , k ] > 0 ) dp [ i , ( j + k ) % A ] += dp [ i - 1 , k ] ; } } }