Given an integer n, your task is to count how many strings of length n can be formed under the following rules:


	Each character is a lower case vowel&nbsp;('a', 'e', 'i', 'o', 'u')
	Each vowel&nbsp;'a' may only be followed by an 'e'.
	Each vowel&nbsp;'e' may only be followed by an 'a'&nbsp;or an 'i'.
	Each vowel&nbsp;'i' may not be followed by another 'i'.
	Each vowel&nbsp;'o' may only be followed by an 'i' or a&nbsp;'u'.
	Each vowel&nbsp;'u' may only be followed by an 'a'.


Since the answer&nbsp;may be too large,&nbsp;return it modulo 10^9 + 7.

&nbsp;
Example 1:

Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".


Example 2:

Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".


Example 3:&nbsp;

Input: n = 5
Output: 68

&nbsp;
Constraints:


	1 &lt;= n &lt;= 2 * 10^4


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        # dp[i][j] means the number of strings of length i that ends with the j-th vowel.
        dp = [[1] * 5] + [[0] * (5) for _ in range(n - 1)]
        moduler = math.pow(10, 9) + 7
        for i in range(1, n):
            # For vowel a
            dp[i][0] = (dp[i - 1][1] + dp[i - 1][2] + dp[i - 1][4]) % moduler
            # For vowel e
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % moduler
            # For vowel i
            dp[i][2] = (dp[i - 1][1] + dp[i - 1][3]) % moduler
            # For vowel o
            dp[i][3] = (dp[i - 1][2]) % moduler
            # For vowel u
            dp[i][4] = (dp[i - 1][2] + dp[i - 1][3]) % moduler

        return int(sum(dp[-1]) % moduler)
class Solution {
    private long[][] dp;
    private int mod = (int)1e9 + 7;

    public int countVowelPermutation(int n) {
        dp = new long[6][n+1];
        if(n == 1) return 5;

        for(int i = 0; i < 5; i++)
            dp[i][0] = 1;

        helper(n,'z');
        return (int)dp[5][n];
    }

    private long helper(int n, char vowel)
    {
        long ans = 0;
        if(n == 0) return 1;

        if(vowel == 'z') // we are using z for our convenience just to add Permutations of all Vowels
        {
            ans = (ans + helper(n-1,'a') + helper(n-1,'e') + helper(n-1,'i') + helper(n-1,'o') + helper(n-1,'u'))%mod;
            dp[5][n] = ans;
        }
        // from here as per our assumptions of Vowels we will make calls & store results
        else if(vowel == 'a') // for Nth number we would store Result for "a" in dp[0][n]
        {
            if(dp[0][n] != 0) return dp[0][n];
            ans = (ans + helper(n-1,'e'))%mod;
            dp[0][n] = ans;
        }

        else if(vowel == 'e') // for Nth number we would store Result for "e" in dp[1][n]
        {
            if(dp[1][n] != 0) return dp[1][n];
            ans = (ans + helper(n-1,'a') + helper(n-1,'i'))%mod;
            dp[1][n] = ans;
        }

        else if(vowel == 'i') // for Nth number we would store Result for "i" in dp[2][n]
        {
            if(dp[2][n] != 0) return dp[2][n];
            ans = (ans + helper(n-1,'a') + helper(n-1,'e') + helper(n-1,'o') + helper(n-1,'u'))%mod;
            dp[2][n] = ans;
        }

        else if(vowel == 'o') // for Nth number we would store Result for "o" in dp[3][n]
        {
            if(dp[3][n] != 0) return dp[3][n];
            ans = (ans + helper(n-1,'i') + helper(n-1,'u'))%mod;
            dp[3][n] = ans;
        }

        else // for Nth number we would store Result for "u" in dp[4][n]
        {
            if(dp[4][n] != 0) return dp[4][n];
            ans = (ans + helper(n-1,'a'))%mod;
            dp[4][n] = ans;
        }

        return ans;
    }
}
class Solution {
public:
    int countVowelPermutation(int n) {
        long a = 1, e = 1, i = 1, o = 1, u = 1, mod = pow(10, 9)+7;
        long a2, e2, i2, o2, u2;

        for (int j = 2; j <= n; j++) {
            a2 = (e + i + u) % mod;
            e2 = (a + i) % mod;
            i2 = (e + o) % mod;
            o2 = i;
            u2 = (o + i) % mod;

            a = a2, e = e2, i = i2, o = o2, u = u2;
        }

        return (a + e + i + o + u) % mod;
    }
};
var countVowelPermutation = function(n) {
    let a = 1, e = 1, i = 1, o = 1, u = 1, mod = 1000000007
    while(n-- > 1){
        let new_a = a % mod, new_e = e % mod, new_i = i % mod, new_o = o % mod, new_u = u % mod
        a = new_e + new_i + new_u
        e = new_a + new_i
        i = new_e + new_o
        o = new_i
        u = new_i + new_o
    }
    return (a + e + i + o + u) % mod
};
Count Vowels Permutation