Count all possible N | Function to find the number of vowel permutations possible ; To avoid the large output value ; Initialize 2D dp array ; Initialize dp [ 1 ] [ i ] as 1 since string of length 1 will consist of only one vowel in the string ; Directed graph using the adjacency matrix ; Iterate over the range [ 1 , N ] ; Traverse the directed graph ; Traversing the list ; Update dp [ i + 1 ] [ u ] ; Stores total count of permutations ; Return count of permutations ; Driver code
def countVowelPermutation ( n ) : NEW_LINE INDENT MOD = 1e9 + 7 NEW_LINE dp = [ [ 0 for i in range ( 5 ) ] for j in range ( n + 1 ) ] NEW_LINE for i in range ( 5 ) : NEW_LINE INDENT dp [ 1 ] [ i ] = 1 NEW_LINE DEDENT relation = [ [ 1 ] , [ 0 , 2 ] , [ 0 , 1 , 3 , 4 ] , [ 2 , 4 ] , [ 0 ] ] NEW_LINE for i in range ( 1 , n , 1 ) : NEW_LINE INDENT for u in range ( 5 ) : NEW_LINE INDENT dp [ i + 1 ] [ u ] = 0 NEW_LINE for v in relation [ u ] : NEW_LINE INDENT dp [ i + 1 ] [ u ] += dp [ i ] [ v ] % MOD NEW_LINE DEDENT DEDENT DEDENT ans = 0 NEW_LINE for i in range ( 5 ) : NEW_LINE INDENT ans = ( ans + dp [ n ] [ i ] ) % MOD NEW_LINE DEDENT return int ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 2 NEW_LINE print ( countVowelPermutation ( N ) ) NEW_LINE DEDENT