Number of ways to color N | Python3 program for the above approach ; Function to count the ways to color block ; For storing powers of 2 ; For storing binomial coefficient values ; Calculating binomial coefficient using DP ; Calculating powers of 2 ; Sort the indices to calculate length of each section ; Initialise answer to 1 ; Find the length of each section ; Merge this section ; Return the final count ; Driver Code ; Number of blocks ; Number of colored blocks ; Function call
mod = 1000000007 NEW_LINE def waysToColor ( arr , n , k ) : NEW_LINE INDENT global mod NEW_LINE powOf2 = [ 0 for i in range ( 500 ) ] NEW_LINE c = [ [ 0 for i in range ( 500 ) ] for j in range ( 500 ) ] NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT c [ i ] [ 0 ] = 1 ; NEW_LINE for j in range ( 1 , i + 1 ) : NEW_LINE INDENT c [ i ] [ j ] = ( c [ i - 1 ] [ j ] + c [ i - 1 ] [ j - 1 ] ) % mod ; NEW_LINE DEDENT DEDENT powOf2 [ 0 ] = 1 NEW_LINE powOf2 [ 1 ] = 1 ; NEW_LINE for i in range ( 2 , n + 1 ) : NEW_LINE INDENT powOf2 [ i ] = ( powOf2 [ i - 1 ] * 2 ) % mod ; NEW_LINE DEDENT rem = n - k ; NEW_LINE arr [ k ] = n + 1 ; NEW_LINE k += 1 NEW_LINE arr . sort ( ) NEW_LINE answer = 1 ; NEW_LINE for i in range ( k ) : NEW_LINE INDENT x = 0 NEW_LINE if i - 1 >= 0 : NEW_LINE INDENT x = arr [ i ] - arr [ i - 1 ] - 1 NEW_LINE DEDENT else : NEW_LINE INDENT x = arr [ i ] - 1 NEW_LINE DEDENT answer = answer * ( c [ rem ] [ x ] % mod ) * ( ( powOf2 [ x ] if ( i != 0 and i != k - 1 ) else 1 ) ) % mod NEW_LINE rem -= x ; NEW_LINE DEDENT return answer ; NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 6 ; NEW_LINE K = 3 ; NEW_LINE arr = [ 1 , 2 , 6 , 0 ] NEW_LINE print ( waysToColor ( arr , N , K ) ) NEW_LINE DEDENT