Number of ways to color N | Python3 program for the above approach ; Recursive function to count the ways ; Base case ; Initialise answer to 0 ; Color each uncolored block according to the given condition ; If any block is uncolored ; Check if adjacent blocks are colored or not ; Color the block ; recursively iterate for next uncolored block ; Uncolored for the next recursive call ; Return the final count ; Function to count the ways to color block ; Mark which blocks are colored in each recursive step ; Function call to count the ways ; Driver Code ; Number of blocks ; Number of colored blocks ; Function call
mod = 1000000007 NEW_LINE def countWays ( colored , count , n ) : NEW_LINE INDENT if ( count == n ) : NEW_LINE INDENT return 1 NEW_LINE DEDENT answer = 0 NEW_LINE for i in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( colored [ i ] == 0 ) : NEW_LINE INDENT if ( colored [ i - 1 ] == 1 or colored [ i + 1 ] == 1 ) : NEW_LINE INDENT colored [ i ] = 1 NEW_LINE answer = ( ( answer + countWays ( colored , count + 1 , n ) ) % mod ) NEW_LINE colored [ i ] = 0 NEW_LINE DEDENT DEDENT DEDENT return answer NEW_LINE DEDENT def waysToColor ( arr , n , k ) : NEW_LINE INDENT colored = [ 0 ] * ( n + 2 ) NEW_LINE for i in range ( k ) : NEW_LINE INDENT colored [ arr [ i ] ] = 1 NEW_LINE DEDENT return countWays ( colored , k , n ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT N = 6 NEW_LINE K = 3 NEW_LINE arr = [ 1 , 2 , 6 ] NEW_LINE print ( waysToColor ( arr , N , K ) ) NEW_LINE DEDENT