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 ('a', 'e', 'i', 'o', 'u')
Each vowel 'a' may only be followed by an 'e'.
Each vowel 'e' may only be followed by an 'a' or an 'i'.
Each vowel 'i' may not be followed by another 'i'.
Each vowel 'o' may only be followed by an 'i' or a 'u'.
Each vowel 'u' may only be followed by an 'a'.

Since the answer may be too large, return it modulo 10^9 + 7.
 
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: 
Input: n = 5
Output: 68
 
Constraints:

1 <= n <= 2 * 10^4

Difficulty: interview

Starter code:

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        

Solutions:
class Solution:
    def countVowelPermutation(self, n: int) -> int:
        a = 1
        e = 1
        i = 1
        o = 1
        u = 1
        res = 0
        M = 1e9+7

        for x in range(n-1):
            a1 = e
            e1 = (a + i) % M
            i1 = (a + e + u + o) % M
            o1 = (i + u) % M
            u1 = a
            a = a1
            e = e1
            i = i1
            o = o1
            u = u1
        
        res = int((a+e+i+o+u) % M)
        return res

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        a, e, i, o, u = 1, 1, 1, 1, 1
        kMod = 1e9+7
        for k in range(2, n+1):
            aa = (e + i + u) % kMod
            ee = (a + i) % kMod
            ii = (e + o) % kMod
            oo = i % kMod
            uu = (i + o) % kMod
            a = aa
            e = ee
            i = ii
            o = oo
            u = uu
        return int((a + e + i + o + u) % kMod)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        last = [1]*5
        MOD = 1e9+7
        for i in range(1, n):
            tempLast = [0]*5
            tempLast[0] = (last[1]+last[2]+last[4])%MOD
            tempLast[1] = (last[0]+last[2])%MOD
            tempLast[2] = (last[1]+last[3])%MOD
            tempLast[3] = (last[2])%MOD
            tempLast[4] = (last[3] + last[2])%MOD
            last = tempLast
        return int(sum(last)%MOD)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        follows = {'a': 'e', 'e': 'ai', 'i': 'aeou', 'o': 'iu', 'u': 'a'}
        dp = dict.fromkeys('aeiou', 1)
        for i in range(n - 1):
            dp1 = dict.fromkeys('aeiou', 0)
            for j in 'aeiou':
                dp1[j] = sum(dp[k] for k in follows[j]) % MOD
            dp = dp1
        return sum(dp.values()) % MOD

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = dict.fromkeys(('a', 'e', 'i', 'o', 'u'), 1)
        for k in range(1, n):
            dp.update(a=sum(dp[v] for v in ('e', 'i', 'u')),
                      e=sum(dp[v] for v in ('a', 'i')),
                      i=sum(dp[v] for v in ('e', 'o')),
                      o=dp['i'],
                      u=sum(dp[v] for v in ('i', 'o')))
        return sum(dp.values()) % (10 ** 9 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        vowels = ['a', 'e', 'i', 'o', 'u']
        MOD = 7 + 1e9
        @lru_cache(maxsize=None)
        def helper(step, char):
            if step == n:
                return 1
            
            result = 0
            if step == 0:
                for currChar in vowels:
                    result = (result + helper(step + 1, currChar)) % MOD
            else:
                if char == 'a':
                    result = (result + helper(step + 1, 'e')) % MOD
                elif char == 'e':
                    result = (result + helper(step + 1, 'a')) % MOD
                    result = (result + helper(step + 1, 'i')) % MOD
                elif char == 'i':
                    for currChar in vowels:
                        if currChar == 'i':
                            continue
                        result = (result + helper(step + 1, currChar)) % MOD
                elif char == 'o':
                    result = (result + helper(step + 1, 'i')) % MOD
                    result = (result + helper(step + 1, 'u')) % MOD
                elif char == 'u':
                    result = (result + helper(step + 1, 'a')) % MOD
            return result
        return int(helper(0, ''))

def solve(n, c, mem):
    if (n, c) in mem:
        return mem[(n, c)]
    if n == 0:
        res = 1
    elif c == 'a':
        res = solve(n-1, 'e', mem) % (10**9 + 7)
    elif c == 'e':
        res = (solve(n-1, 'a', mem)+solve(n-1, 'i', mem)) % (10**9 + 7)
    elif c == 'i':
        a = solve(n-1, 'a', mem)
        e = solve(n-1, 'e', mem)
        o = solve(n-1, 'o', mem)
        u = solve(n-1, 'u', mem)
        res = (a+e+o+u) % (10**9 + 7)
    elif c == 'o':
        res = (solve(n-1, 'i', mem) + solve(n-1, 'u', mem))% (10**9 + 7)
    else:
        res = solve(n-1, 'a', mem) % (10**9 + 7)
    
    mem[(n, c)] = res
    return res

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        mem = {}
        return sum(solve(n-1, c, mem) for c in {'a', 'e', 'i', 'o', 'u'}) % (10**9 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = [[0]*5 for i in range(n)]
        for i in range(len(dp[0])):
            dp[0][i] = 1 
        dic = {'a':'e','e':'ai','i':'aeou','o':'iu','u':'a'}
        mapping = {'a':0,'e':1,'i':2,'o':3,'u':4}
        for i in range(1,n):
            for char in 'aeiou':
                inda = mapping[char]
                for val in dic[char]:
                    indb = mapping[val]
                    dp[i][indb] += dp[i-1][inda]
        return sum(dp[-1])%(10**9 + 7)
        
        
        
        


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = [[0]*5 for _ in range(n)]
        for i in range(5):
            dp[0][i] = 1
        vowels = ['a','e','i','o','u']
        for i in range(1,n):
            for idx,vowel in enumerate(vowels):
                if vowel == 'a':
                    dp[i][idx] += dp[i-1][1] + dp[i-1][2] + dp[i-1][4]
                if vowel == 'e':
                    dp[i][idx] += dp[i-1][0] + dp[i-1][2]
                if vowel == 'i':
                    dp[i][idx] += dp[i-1][1] + dp[i-1][3]
                if vowel == 'o':
                    dp[i][idx] += dp[i-1][2]
                if vowel == 'u':
                    dp[i][idx] += dp[i-1][2] + dp[i-1][3]
                    
        return sum(dp[n-1]) % (10**9 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        mod = 10**9 + 7
        
        @lru_cache(None)
        def go(ch, n):
            if n == 0:
                return 1            
            if (ch =='a'):
                return go('e', n - 1)
            elif (ch == 'e'):
                return go('a', n - 1) + go('i', n - 1)
            elif (ch == 'i'):
                return go('a', n - 1) + go('e', n - 1) + go('o', n - 1) + go('u', n - 1)
            elif (ch == 'o'):
                return go('i', n - 1) + go('u', n - 1)
            else:
                return go('a', n - 1)
            
        res1 = go('a', n - 1) % mod
        res2 = go('e', n - 1) % mod 
        res3 = go('i', n - 1) % mod
        res4 = go('o', n - 1) % mod
        res5 = go('u', n - 1) % mod
        
        return (res1 + res2 + res3 + res4 + res5) % mod
            


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        a, e, i, o, u = 1,1,1,1,1
        p = 10**9+7
        def next(a, e, i, o, u):
           # a, e, i, o, u = row
            e, a, i, o, u = (a+i) % p, (e+i+u)%p, (e+o) % p, i % p, (i+o) % p
           # row = [a, e, i, o, u]
            return a, e, i, o, u
        l = 1
        while l < n:
            a, e, i, o, u = next(a, e, i, o, u)
            l+=1
        return (a+e+i+o+u) % p


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dic = {}
        dic['a'] = ['e']
        dic['e'] = ['a','i']
        dic['i'] = ['a','e','o','u']
        dic['o'] = ['i','u']
        dic['u'] = ['a']
        vowels = ['a','e','i','o','u']
        dp = {}
        for v in vowels:
            dp[(v,1)] = 1
        
        for i in range(2,n+1):
            for v in vowels:
                for followed in dic[v]:
                    dp[(v,i)] = (dp.get((v,i),0) + dp[(followed,i-1)]) % (10**9 + 7)
        res = 0
        for v in vowels:
            res += dp[(v,n)]
        return res % (10**9 + 7)
            
            
        
#         def helper(vowel,depth):
#             if depth == 0:
#                 return 1
#             res = 0
#             for v in dic[vowel]:
#                 res += helper(v, depth-1)
#             return res
#         res = 0
#         for v in ['a']


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        memo = {}
        def f(i, prev_vowel):
            if i == n:
                return 1
            
            if (i, prev_vowel) in memo:
                return memo[(i, prev_vowel)]
            
            cnt = 0
            if prev_vowel == 'a':
                cnt += f(i + 1, 'e')
            elif prev_vowel == 'e':
                cnt += f(i + 1, 'a') + f(i + 1, 'i')
            elif prev_vowel == 'i':
                cnt += f(i + 1, 'a') + f(i + 1, 'e') + f(i + 1, 'o') + f(i + 1, 'u')
            elif prev_vowel == 'o':
                cnt += f(i + 1, 'i') + f(i + 1, 'u')
            else:
                cnt += f(i + 1, 'a')
                
            memo[(i, prev_vowel)] = cnt % (10**9 + 7)
            return cnt
        
        cnt = 0
        for vowel in ['a', 'e', 'i', 'o', 'u']:
            cnt += f(1, vowel)
        
        return cnt % (10**9 + 7)



class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = {}
        for v in ('a', 'e', 'i', 'o', 'u'):
            dp[v] = [1] + [0] * (n - 1)
        for i in range(1, n):
            dp['a'][i] = sum(dp[v][i-1] for v in ('e', 'i', 'u'))
            dp['e'][i] = sum(dp[v][i-1] for v in ('a', 'i'))
            dp['i'][i] = sum(dp[v][i-1] for v in ('e', 'o'))
            dp['o'][i] = dp['i'][i-1]
            dp['u'][i] = sum(dp[v][i-1] for v in ('i', 'o'))
        return sum(row[-1] for row in dp.values()) % (10 ** 9 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        f = [[0 for _ in range(5)] for _ in range(n + 1)]
        for i in range(5):
            f[1][i] = 1
        index = {'a':0,'e':1,'i':2,'o':3,'u':4}
        letter = ['a','e','i','o','u']
        pre = {'a':['e','i','u'],
                  'e':['a','i'],
                  'i':['e','o'],
                  'o':['i'],
                  'u':['i','o']}
        for i in range(2, n + 1):
            for j in range(5):
                tmp = 0
                for k in pre[letter[j]]:
                    tmp += f[i - 1][index[k]]
                f[i][j] = tmp
        return sum(f[n]) % (10**9 + 7)
            


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        @lru_cache(None)
        def dfs(i, j):
            if i == 1:
                return 1
            if j == 'a':
                return dfs(i - 1, 'e') + dfs(i - 1, 'i') + dfs(i - 1, 'u')
            elif j == 'e':
                return dfs(i - 1, 'a') + dfs(i - 1, 'i')
            elif j == 'i':
                return dfs(i - 1, 'e') + dfs(i - 1, 'o')
            elif j == 'o':
                return dfs(i - 1, 'i')
            
            return dfs(i - 1, 'i') + dfs(i - 1, 'o')
        
        return sum(dfs(n, i) for i in ('a', 'e', 'i', 'o', 'u')) % (10 ** 9 + 7)

from collections import defaultdict


class Solution:

    MOD = 10**9 + 7

    def __init__(self):
        self.cache = defaultdict(dict)

    def countVowelPermutation(self, n: int) -> int:
        return self.count(n)

    def count(self, n: int, vowel: str = None) -> int:
        if n == 0:
            return 1

        if vowel in self.cache[n]:
            return self.cache[n][vowel]

        count = 0
        if vowel == 'a':
            count = self.count(n - 1, 'e')
        elif vowel == 'e':
            count = self.count(n - 1, 'a')
            count += self.count(n - 1, 'i')
        elif vowel == 'i':
            count = self.count(n - 1, 'a')
            count += self.count(n - 1, 'e')
            count += self.count(n - 1, 'o')
            count += self.count(n - 1, 'u')
        elif vowel == 'o':
            count = self.count(n - 1, 'i')
            count += self.count(n - 1, 'u')
        elif vowel == 'u':
            count = self.count(n - 1, 'a')
        elif vowel is None:
            count = self.count(n - 1, 'a')
            count += self.count(n - 1, 'e')
            count += self.count(n - 1, 'i')
            count += self.count(n - 1, 'o')
            count += self.count(n - 1, 'u')
        count %= self.MOD
        self.cache[n][vowel] = count
        return count


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        
        def count(i, v, mem):
            key = (i, v)
            if key in mem: return mem[key]

            if i == n-1:
                mem[key] = 1
                return mem[key]

            ans = 0
            if v == 'a':
                ans += count(i+1, 'e', mem)
            elif v == 'e':
                ans += count(i+1, 'a', mem)
                ans += count(i+1, 'i', mem)
            elif v == 'i':
                ans += count(i+1, 'a', mem)
                ans += count(i+1, 'e', mem)
                ans += count(i+1, 'o', mem)
                ans += count(i+1, 'u', mem)
            elif v == 'o':
                ans += count(i+1, 'i', mem)
                ans += count(i+1, 'u', mem)
            elif v == 'u':
                ans += count(i+1, 'a', mem)
            mem[key] = ans % (10 ** 9 + 7)
            return mem[key]
        
        mem = {}
        ans = count(0, 'a', mem) + count(0, 'e', mem) + count(0,'i', mem) + count(0,'o', mem) + count(0,'u', mem)
        return ans % (10 ** 9 + 7)

class Solution:
    dp = [dict.fromkeys('aeiou', 1)]
    def countVowelPermutation(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        follows = {'a': 'e', 'e': 'ai', 'i': 'aeou', 'o': 'iu', 'u': 'a'}
        for i in range(len(self.dp), n):
            dp1 = dict.fromkeys('aeiou', 0)
            for j in 'aeiou':
                dp1[j] = sum(self.dp[-1][k] for k in follows[j]) % MOD
            self.dp.append(dp1)
        return sum(self.dp[n - 1].values()) % MOD

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        MOD = (10**9 + 7)
        mapping = [
            [1,2,4], [0, 2], [1, 3], [2], [2, 3]
        ]
        dp = [[0 for _ in range(5)] for _ in range(n)]
        for i in range(len(dp)):
            for j in range(len(dp[0])):
                if i == 0:
                    dp[i][j] = 1
                    continue
                for prev in mapping[j]:
                    dp[i][j] += dp[i - 1][prev]
        return sum(dp[n - 1]) % MOD

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        
        d = {'a':1,'e':2,'i':3,'o':4,'u':5}
        
        @lru_cache(maxsize=None)
        def f(n, i):
            if n == 0:
                return 1
            if i == d['a']:
                return f(n-1, d['e'])
            if i == d['e']:
                return f(n-1, d['a']) + f(n-1, d['i'])
            if i == d['i']:
                return f(n-1, d['a']) + f(n-1, d['e']) + f(n-1, d['o']) + f(n-1, d['u'])
            if i == d['o']:
                return f(n-1, d['i']) + f(n-1, d['u'])
            if i == d['u']:
                return f(n-1, d['a'])
            
        if n == 0: return 0
        ans = 0
        for k, v in d.items():
            ans += f(n-1, v)
        return ans % (10**9 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        
        graph={'a':['e'],'e':['a','i'],'i':['a','e','o','u'],'o':['i','u'],'u':['a']}
        dp=[[None for j in range(5)] for i in range(n+1)]
        get={'a':0,'e':1,'i':2,'o':3,'u':4}
        mod=int(10**9)+7
        
        def dfs(n,node):
            if n==1:
                return 1
            elif dp[n][get[node]]:
                return dp[n][get[node]]
            else:
                ans=0
                for w in graph[node]:
                    ans+=dfs(n-1,w)%mod
                dp[n][get[node]]=ans
                return ans
                    
        x=0
        for b in 'aeiou':
            x+=dfs(n,b)%mod
        return x%mod


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = [[0 for i in range(5)] for j in range(n)]
        for i in range(5):
            dp[-1][i] = 1
        
        d = {
            0: [1],
            1: [0, 2],
            2: [0, 1, 3, 4],
            3: [2, 4],
            4: [0]
        }
        # print(dp)
        for i in range(n-2, -1, -1):
            for j in range(5):
                c = 0
                for e in d[j]:
                    c += dp[i+1][e]
                dp[i][j] = c
        # print(dp)
        return (dp[0][0] + dp[0][1] + dp[0][2] + dp[0][3] + dp[0][4])%(1000000007)


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        
        vtoi = {'a':0, 'e':1, 'i':2, 'o':3, 'u':4}
        itov = {0:'a', 1:'e', 2:'i', 3:'o', 4:'u'}
        
        prev = {'a': ['e', 'i', 'u'],
                'e': ['a', 'i'],
                'i': ['e', 'o'],
                'o': ['i'],
                'u': ['i', 'o']}
        dp = [[0 for _ in range(5)] for _ in range(n+1)]
        
        for j in range(5):
            dp[1][j] = 1
        
        for i in range(2, n+1):
            for j in range(5):
                for p in prev[itov[j]]:
                    dp[i][j] += dp[i-1][vtoi[p]]
    
        return sum(dp[-1]) % (10**9+7)
                
                


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = {}
        dp[1] = {}
        for c in ['a', 'e', 'i', 'o', 'u']:
            dp[1][c] = 1
        sources = {}
        sources['a'] = ['e','i','u']
        sources['e'] = ['a', 'i']
        sources['i'] = ['e', 'o']
        sources['o'] = ['i']
        sources['u'] = ['i', 'o']
        for i in range(2, n+1):
            dp[i] = {}
            for c in ['a', 'e', 'i', 'o', 'u']:
                dp[i][c] = sum(
                    dp[i-1][s] for s in sources[c]
                )
        return sum(dp[n][c] for c in dp[n])  % 1000000007


class Solution:
    mod=(10)**9+7
    relation=[[1,2,4],[0,2],[1,3],[2],[2,3]]
    def dfs(self,n,v):
        memo=self.memo
        if n==1:
            return 1
        if memo[n][v]!=-1:
            return memo[n][v]
        memo[n][v]=0
        ans=0
        for i in self.relation[v]:
            ans=(ans+self.dfs(n-1,i))%self.mod
        memo[n][v]=ans
        return ans
        
            
    def countVowelPermutation(self, n: int) -> int:
        self.memo=[[-1 for _ in range(5)] for _ in range(n+1)]
        res=0
        for i in range(5):
            res=(res+self.dfs(n,i))%self.mod
        return res            
         
        
        
        
        
        


class Solution:
    dp = [[1] * 5]
    def countVowelPermutation(self, n: int) -> int:
        MOD = 10 ** 9 + 7
        follows = {0: [1], 1: [0, 2], 2: [0, 1, 3, 4], 3: [2, 4], 4: [0]}
        for i in range(len(self.dp), n):
            dp1 = [0] * 5
            for j in range(5):
                dp1[j] = sum(self.dp[-1][k] for k in follows[j]) % MOD
            self.dp.append(dp1)
        return sum(self.dp[n - 1]) % MOD

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        MOD = (10 ** 9 + 7)
        vows = 'aeiou'
        mapping = {
            0: [1], # a
            1: [0 ,2], # e
            2: [0, 1, 3, 4], # i
            3: [2, 4], # o
            4: [0] # u
        }
        dp = [[0 for _ in range(len(vows))] for _ in range(n)]
        dp[0] = [1] * len(vows)
        for i in range(1, len(dp)):
            for j in range(len(dp[0])):
                for next_ch in mapping[j]:
                    dp[i][j] += dp[i - 1][next_ch]
        return sum(dp[-1]) % MOD


class Solution:
    def countVowelPermutation(self, n: int) -> int:    
        mod = (10**9+7)
        
        
        @lru_cache
        def dfs(p, n):
            if n == 0:
                return 1
            
            if p == 'a':
                return dfs('e', n-1)
            if p == 'e':
                return sum([dfs(c, n-1) for c in ['a', 'i']])        
            if p == 'i':
                return sum([dfs(c, n-1) for c in ['a', 'e', 'o', 'u']])   
            elif p == 'o':
                return sum([dfs(c, n-1) for c in ['i', 'u']])
            else: # u
                return dfs('a', n-1)
        
        return sum([dfs(c, n-1) for c in ['a', 'e', 'i', 'o', 'u']]) % mod

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dic = {}
        dic['a'] = ['e']
        dic['e'] = ['a','i']
        dic['i'] = ['a','e','o','u']
        dic['o'] = ['i','u']
        dic['u'] = ['a']
        vowels = ['a','e','i','o','u']
        dp = {}
        for v in vowels:
            dp[(v,1)] = 1
        
        for i in range(2,n+1):
            for v in vowels:
                for followed in dic[v]:
                    dp[(v,i)] = dp.get((v,i),0) + dp[(followed,i-1)]
        res = 0
        for v in vowels:
            res += dp[(v,n)]
        return res % (10**9 + 7)
            
            
        
#         def helper(vowel,depth):
#             if depth == 0:
#                 return 1
#             res = 0
#             for v in dic[vowel]:
#                 res += helper(v, depth-1)
#             return res
#         res = 0
#         for v in ['a']


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        if n <= 1:
            return n * 5
        start_table = {0: [1], 1: [0, 2], 2: [0, 1, 3, 4], 3: [2, 4], 4: [0]}
        dp = [[0] * 5 for i in range(n + 1)]
        for i in range(5):
            dp[1][i] = 1
        for i in range(2, n+1):
            for j in range(5):
                after = start_table[j]
                dp[i][j] = sum(dp[i-1][v] for v in after)
        return sum(dp[-1]) % (10**9 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:    
        mod = (10**9+7)
        mem = {}
        
        
        def dfs(p, n):
            if (p, n) in mem:
                return mem[(p,n)]
            if n == 0:
                return 1
            
            res = 0
            if p == 'a':
                res = dfs('e', n-1)
            elif p == 'e':
                res = sum([dfs(c, n-1) for c in ['a', 'i']])        
            elif p == 'i':
                res = sum([dfs(c, n-1) for c in ['a', 'e', 'o', 'u']])   
            elif p == 'o':
                res = sum([dfs(c, n-1) for c in ['i', 'u']])
            else: # u
                res = dfs('a', n-1)
            
            mem[(p,n)] = res%mod
            return res%mod
        
        return sum([dfs(c, n-1) for c in ['a', 'e', 'i', 'o', 'u']]) % mod

MOD = int(1e9 + 7)

class Solution:
    def get(self, n, l):
        if n == 1:
            return 1
        
        try:
            return self.cache[(n, l)]
        except KeyError:
            ret = 0
            for next_l in self.next_letters[l]:
                ret += self.get(n - 1, next_l)
                ret %= MOD
                
            self.cache[(n, l)] = ret
            return ret
        
    def countVowelPermutation(self, n: int) -> int:
        self.next_letters = [
            [1],
            [0, 2],
            [0, 1, 3, 4],
            [2, 4],
            [0],
        ]
        self.cache = {}
        
        for nn in range(2, n + 1):
            for l in range(5):
                self.get(nn, l)
        
        ret = 0
        for l in range(5):
            ret += self.get(n, l)
            ret %= MOD
        return ret
        


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        a,e,i,o,u = [1], [1], [1], [1], [1]
        mod = 10**9 + 7
        if n == 0: return 0 
        for top, countDown in enumerate (range (n, 1, -1)):
            a.append (e [top] % mod)
            e.append ((a [top] + i [top]) % mod)
            i.append ((a [top] + e [top] + o [top] + u [top]) % mod)
            o.append ((i [top] + u [top]) % mod)
            u.append (a [top] % mod)
        
        return (a [-1] + e [-1] + i [-1] + o [-1] + u [-1]) % mod

def countVowels(x, n, memo):
    convert = {'a':0, 'e':1, 'i':2, 'o':3, 'u':4}
    x_val = convert[x]
    if n == 1:
        return 1
    if memo[x_val][n] != -1:
        return memo[x_val][n]
    if x == 'a':
        memo[x_val][n] = countVowels('e', n-1, memo)
        return memo[x_val][n]
    elif x == 'u':
        memo[x_val][n] = countVowels('a', n-1, memo)
        return memo[x_val][n]
    elif x == 'e':
        memo[x_val][n] = (countVowels('a', n-1, memo)+countVowels('i', n-1, memo))
        return memo[x_val][n]
    elif x == 'o':
        memo[x_val][n] = (countVowels('i', n-1, memo)+countVowels('u', n-1, memo))
        return memo[x_val][n]
    elif x == 'i':
        memo[x_val][n] = (countVowels('a', n-1, memo)+countVowels('e', n-1, memo)+countVowels('o', n-1, memo)+countVowels('u', n-1, memo))
        return memo[x_val][n]

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        if n == 1:
            return 5
        else:
            memo = [[-1 for j in range(n+1)] for i in range(5)]
            res = countVowels('a', n, memo) + countVowels('e', n, memo) + countVowels('i', n, memo) + countVowels('o', n, memo) + countVowels('u', n, memo)
            return res%1000000007

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        if n <= 1:
            return n * 5
        # table = {'a': ['e'], 'e': ['a', 'i'], 'i': ['a', 'e', 'o', 'u'], 'o': ['i', 'u'], 'u': ['a']}
        # idx_table = ['a', 'e', 'i', 'o', 'u']
        end_table = {0: [1, 2, 4], 1: [0, 2], 2: [1, 3], 3: [2], 4: [2, 3]}
        dp = [[0] * 5 for i in range(n+1)]
        for i in range(5):
            dp[1][i] = 1
        for i in range(2, n+1):
            for j in range(5):
                before = end_table[j]
                dp[i][j] = sum(dp[i-1][v] for v in before)
        return sum(dp[-1]) % (10**9 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        
        memo = dict()
    
        def helper(char: str, x: int):
            if (char, x) in memo:
                return memo[char, x]
            
            if x == 1:
                memo[char, x] = 1
                return memo[char, x]
            
            if char == 'a':
                memo[char, x] = helper('e', x-1)
            elif char == 'e':
                memo[char, x] = helper('a', x-1) + helper('i', x-1)
            elif char == 'i':
                memo[char, x] = sum(helper(c, x-1) for c in 'aeou')
            elif char == 'o':
                memo[char, x] = helper('i', x-1) + helper('u', x-1)
            elif char == 'u':
                memo[char, x] = helper('a', x-1)
            
            return memo[char, x]
        
        total = sum(helper(c, n) for c in 'aeiou')
        
        return total % (10**9+7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        graph = {'a': ['e'], 'e': ['a', 'i'], 'i': ['a', 'e', 'o', 'u'], 'o':['i', 'u'], 'u':['a']}
        d1={'a':1, 'e':1, 'i':1,'o':1,'u':1}
        
        for i in range(1,n):
            d2={}
            for v, f in d1.items():
                for nxt in graph[v]: 
                    d2[nxt] = d2.get(nxt, 0) + f
            d1 = d2
        return sum(d1.values()) % (10**9+7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        
        dp = {}
        MOD = 10**9 + 7
        
        def helper(pre, n0):
            
            if (pre, n0) in dp:
                return dp[(pre, n0)]
            
            if n0 == 0:
                return 1
            
            if pre == 'a':
                subAns = helper('e', n0-1)
            elif pre == 'e':
                subAns = helper('a', n0-1) + helper('i', n0-1)
            elif pre == 'i':
                subAns = helper('a', n0-1) +helper('e', n0-1) + helper('o', n0-1) + helper('u', n0-1)
            elif pre == 'o':
                subAns = helper('i', n0-1) + helper('u', n0-1)
            else:
                subAns = helper('a', n0-1)
                
            dp[(pre, n0)] = subAns%MOD
            
            return subAns
        
        return (helper('a', n-1) +helper('e', n-1) + helper('i', n-1) + helper('o', n-1) + helper('u', n-1))%MOD

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        a,e,i,o,u = 1,1,1,1,1
        for k in range(1, n):
            a,e,i,o,u = i+e+u, a+i, e+o, i, i+o
        return (a+e+i+o+u) % (10**9 + 7)


        
        
        #***** BRute Force *****#
#         dic = {
#             'e' : {'a','i'},
#             'a' : {'i', 'e', 'u'},
#             'i' : {'e', 'o'},
#             'o' : {'i'},
#             'u' : {'i','o'},
#         }
        
#         def bfs(q, dic, ans):
#             while(q):
#                 vov, dist = q.popleft()
#                 #print(vov, dist)
#                 if(dist == n):
#                     ans = ans + 1
#                 if(dist > n):
#                     break
#                 for ch in dic[vov]:
#                     #print(ch,dist+1, \"*\")
#                     q.append((ch,dist+1))
#                     #visited.add(ch)
#             return ans 
            
        
        
#         result = 0
#         for k in ['a', 'e', 'i', 'o', 'u']:
#             q = deque()
#             q.append((k, 1))
#             # visited = set()
#             # visited.add(k)
#             ans = bfs(q, dic, 0)
#             result = result + ans
            
#         return result


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        res=0
        dp={}
        def rec(l,curr):
            nonlocal dp,res
            if dp.get((l,curr),-1)!=-1:
                res+=dp[l,curr]
                return dp[l,curr]
            if l==0:
                res+=1
                return 1
            if curr=='a':
                m=rec(l-1,'e')
            elif curr=='e':
                m=rec(l-1,'a')+rec(l-1,'i')
            elif curr=='i':
                m=rec(l-1,'a')+rec(l-1,'e')+rec(l-1,'o')+rec(l-1,'u')
            elif curr=='o':
                m=rec(l-1,'u')+rec(l-1,'i')
            else:
                m=rec(l-1,'a')
            dp[l,curr]=m
            return dp[l,curr]
        for i in ['a','e','i','o','u']:
            rec(n-1,i)
        return res%1000000007

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        a, e, i, o, u = 1, 1, 1, 1, 1
        for _ in range(n-1):
             a, e, i, o, u = e + i + u, a + i, e + o, i, i + o
        
        return (a + e + i + o + u) % (10**9 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        a = e = i = o = u = 1
        for p in range(n-1):
            a, e, i, o , u = e + i + u, a + i, e + o, i, i + o
        return (a+e+i+o+u) % (10**9+7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        if not n :
            return 0
        a = e = i = o = u = 1
        for _ in range(n - 1):
            a, e, i, o, u = e, a + i, a + e + o + u, i + u, a
        return (a + e + i + o + u) % (10**9+7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        a, e, i, o, u = 1, 1, 1, 1, 1
        
        for _ in range(n - 1):
            a,e,i,o,u = e + i + u, a + i, e + o, i, i + o
        return (a + e + i + o + u) % (10**9 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        a,e,i,o,u = 1,1,1,1,1
        #store the number of each vowels
        for _ in range(1,n):
            a,e,i,o,u = e+i+u,a+i,e+o,i,i+o
        return (a+e+i+o+u)% 1000000007


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        a, e, i, o, u = 1, 1, 1, 1, 1
        for _ in range(n - 1):
            a, e, i, o, u = e + i + u, a + i, e + o, i, i + o
        return (a + e + i + o + u) % (10**9 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        a,e,i,o,u = 1,1,1,1,1
        for _ in range(n-1):
            a,e,i,o,u = e, a+i, a+e+o+u, i+u, a
        return(a+e+i+o+u)%(10**9+7)

class Solution:
        
    def countVowelPermutation(self, n: int) -> int:
        
        mod = 10**9 + 7
        nstrs = [1] * 5
        
        while n > 1:
            (a, e, i, o, u) = nstrs
            nstrs[0] = e
            nstrs[1] = a + i  
            nstrs[2] = a + e + o + u  
            nstrs[3] = i + u
            nstrs[4] = a 
            
            n -= 1
        
        return sum(nstrs) % mod

class Solution:
    
    
    def countVowelPermutation(self, n: int) -> int:
        
        d = {}
        d['a'] = 1
        d['e'] = 1
        d['i'] = 1
        d['o'] = 1
        d['u'] = 1
        
        for i in range(1,n):
            dx = {}
            dx['a'] = (d['e'] + d['i'] + d['u']) % (10**9+7)
            dx['e'] = (d['a'] + d['i']) % (10**9+7)
            dx['i'] = (d['e'] + d['o']) % (10**9+7)
            dx['o'] = (d['i']) % (10**9+7)
            dx['u'] = (d['i'] + d['o']) % (10**9+7)
            d = dx
        
        r = 0
        for c in d.keys():
            r += (d[c] % (10**9+7))
            
        return r % (10**9+7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dic = {}
        dic['a'] = 1
        dic['e'] = 1
        dic['i'] = 1
        dic['o'] = 1
        dic['u'] = 1
                        
        for j in range(n-1):
            
            counta = dic['e']
            counte = dic['a'] + dic['i']
            counti = dic['e'] + dic['o'] + dic['a'] + dic['u']
            counto = dic['i'] + dic['u']
            countu = dic['a']

            dic['a'] = counta
            dic['e'] = counte
            dic['i'] = counti
            dic['o'] = counto
            dic['u'] = countu
                        
        count = sum([v for k, v in dic.items()])
        
        return count % (10**9 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        
        # from collections import defaultdict
        
        end = dict()
        end['a'] = 1
        end['e'] = 1
        end['i'] = 1
        end['o'] = 1
        end['u'] = 1
                        
        for j in range(n-1):
            
            for_a = end['e'] + end['i'] + end['u']
            for_e = end['a'] + end['i']
            for_i = end['e'] + end['o']
            for_o = end['i']
            for_u = end['o'] + end['i']

            end['a'] = for_a
            end['e'] = for_e
            end['i'] = for_i
            end['o'] = for_o
            end['u'] = for_u
                        
        count = sum([v for k, v in end.items()])
        
        return count % (10**9 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        a = [1] * 5
        b = [1] * 5
        for i in range(1, n):
            b[0] = a[1]
            b[1] = a[0] + a[2]
            b[2] = a[0] + a[1] + a[3] + a[4]
            b[3] = a[2] + a[4]
            b[4] = a[0]
            a = b.copy()
        
        return sum(b) % (10**9 + 7)

'''
Dynamic programing with recursion?

Base case is five. 

[1,1,1,1,1]

a =1 e=2 i=4 o=2 u=1

a,e
e,a | e,i
i,a | i,e | i,u, |i,o
o,i | o,u
u,a

a = 2, e = 5, i = 10 ,o = 5, u =1



Each round, you are calculating the number of permutations a letter has if you were to stick it in front.

for instance: i


for 3 letters:
i: used the previous 
a,e
e,a | e,i
o,i | o,u
u,a

for a total of 6 additional permutations. 



'''


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        #starting count at 2
        prev_count = [1,2,4,2,1]

        
        if n == 1:
            return 5
        
        if n == 2:
            return sum(prev_count)
        
        for i in range(3,n+1):
            #print(prev_count)
            current_count = [0] * 5
            #a
            current_count[0] = prev_count[1]
            #e
            current_count[1] = prev_count[0] + prev_count[2]
            #i
            current_count[2] = prev_count[0] + prev_count[1] + prev_count[3] + prev_count[4] 
            #o
            current_count[3] = prev_count[2] + prev_count[4]
            #u
            current_count[4] = prev_count[0]
            
            #print(current_count)
            prev_count = current_count
        #print(prev_count)
        return sum(current_count) % (10**9 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        from collections import defaultdict
        
        end = dict()
        end['a'] = 1
        end['e'] = 1
        end['i'] = 1
        end['o'] = 1
        end['u'] = 1
                        
        for j in range(n-1):
            
            for_a = end['e'] + end['i'] + end['u']
            for_e = end['a'] + end['i']
            for_i = end['e'] + end['o']
            for_o = end['i']
            for_u = end['o'] + end['i']

            end['a'] = for_a
            end['e'] = for_e
            end['i'] = for_i
            end['o'] = for_o
            end['u'] = for_u
                        
        count = sum([v for k, v in end.items()])
        
        return count % (10**9 + 7)   

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dic = {'a':1,'e':1,'i':1,'o':1,'u':1}
        
        for _ in range(n-1):
            a = dic['e']+dic['i']+dic['u']
            e = dic['a']+dic['i']
            i = dic['e']+dic['o']
            o = dic['i']
            u = dic['o']+dic['i']
            
            dic['a'] = a
            dic['e'] = e
            dic['i'] = i
            dic['o'] = o
            dic['u'] = u
        count = 0   
        for value in (list(dic.values())):
            count+=value
        return count % (10**9 + 7)


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        pos=[1,1,1,1,1]
        newpos=[1,1,1,1,1]
        for i in range(1,n):
            newpos[0]=pos[1]+pos[2]+pos[4]
            newpos[1]=pos[0]+pos[2]
            newpos[2]=pos[1]+pos[3]
            newpos[3]=pos[2]
            newpos[4]=pos[2]+pos[3]

            pos[0]=newpos[0]
            pos[1]=newpos[1]
            pos[2]=newpos[2]
            pos[3]=newpos[3]
            pos[4]=newpos[4]
        return ((newpos[0]+newpos[1]+newpos[2]+newpos[3]+newpos[4])% (10**9 + 7))

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        
        from collections import defaultdict
        
        end = dict()
        end['a'] = 1
        end['e'] = 1
        end['i'] = 1
        end['o'] = 1
        end['u'] = 1
                        
        for j in range(n-1):
            
            for_a = end['e'] + end['i'] + end['u']
            for_e = end['a'] + end['i']
            for_i = end['e'] + end['o']
            for_o = end['i']
            for_u = end['o'] + end['i']

            end['a'] = for_a
            end['e'] = for_e
            end['i'] = for_i
            end['o'] = for_o
            end['u'] = for_u
                        
        count = sum([v for k, v in end.items()])
        
        return count % (10**9 + 7)      

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        '''       
        # TLE top-down
        graph = {'a': ['e'], 'e':['a', 'i'],\\
                'i': ['a','e','o','u'], 'o': ['i', 'u'],\\
                'u': ['a']}
        mod = 10**9+7
        @functools.lru_cache(None)
        def dp(c, i):
            if i == 1:
                return 1
            return sum(dp(key, i-1) for key in graph[c])%mod
        return sum(dp(key, n) for key in graph)%mod
        '''
        a, e, i, o, u = 1, 1, 1, 1, 1
        for _ in range(1, n):
            a, e, i, o, u = e + i + u, a + i, e + o, i, i + o
        return (a + e + i + o + u) % (10**9 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = [1] * 5
        mod = 1000000007
        for i in range(n - 1):
            next = [0] * 5
            
            next[1] += dp[0]

            next[0] += dp[1]
            next[2] += dp[1]

            next[0] += dp[2]
            next[1] += dp[2]
            next[3] += dp[2]
            next[4] += dp[2]

            next[2] += dp[3]
            next[4] += dp[3]

            next[0] += dp[4]

            for j in range(5):
                next[j] = next[j] % mod
            dp = next
        return sum(dp) % mod

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        if n < 1: return 0
        f = [[0]*5, [0]*5]
        f[1&1] = [1]*5
        vowel = 'aeoui'
        
        for i in range(2,n+1):
            f[i&1][0] = (f[(i-1)&1][3] + f[(i-1)&1][1] + f[(i-1)&1][4]) % (10**9 + 7)
            f[i&1][1] = (f[(i-1)&1][0] + f[(i-1)&1][4]) % (10**9 + 7)
            f[i&1][2] = f[(i-1)&1][4] % (10**9 + 7)
            f[i&1][3] = (f[(i-1)&1][2] + f[(i-1)&1][4]) % (10**9 + 7)
            f[i&1][4] = (f[(i-1)&1][1] + f[(i-1)&1][2]) % (10**9 + 7)
        return sum(f[n&1]) % (10**9 + 7)


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        
        #drawing graph
        # a -> e
        # e -> a, i
        # i -> a, e, o, u
        # o -> i, u
        # u -> a
        
        # 'a' can follow {'e', 'i', 'u'}
        # 'e' can follow {'a', 'i'}
        # 'i' can follow {'e', 'o'}
        # 'o' can follow {'i'}
        # 'u' can follow {'i', 'o'}
           
        mod = 10**9+7
        count = 0
        
        #cols = the 5 vowels, rows = length of string
        #i,j coord denotes num of valid strings of length i
        #col 0 = a, 1 = e, 2, = i, 3 = o, 4 = u
        dp = [[0 for i in range(5)] for j in range(n+1)]
        
        for i in range(5):
            dp[1][i] = 1
            
        for i in range(1, n):
            dp[i+1][0] = (dp[i][1] + dp[i][2] + dp[i][4]) % mod
            dp[i+1][1] = (dp[i][0] + dp[i][2]) % mod
            dp[i+1][2] = (dp[i][1] + dp[i][3]) % mod
            dp[i+1][3] = (dp[i][2]) % mod
            dp[i+1][4] = (dp[i][2] + dp[i][3]) % mod
        
        for i in range(5):
            count = (count + dp[n][i]) % mod
        
        return count
            
            
            
            
            
            
        
        
        
        
        
        
        
        
        


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        a = 1
        e = 1
        i = 1
        o = 1
        u = 1
        kmod = pow(10, 9) + 7
        
        for k in range(2, n + 1):
            aa = (e + i + u) % kmod
            ee = (a + i) % kmod
            ii = (e + o) % kmod
            oo = i % kmod
            uu = (i + o) % kmod
            a = aa
            e = ee
            i = ii
            o = oo
            u = uu
        
        return sum([a, e, i, o, u]) % kmod

from enum import IntEnum

class Solution:
        
    found, not_found = 0, 0
        
    def countVowelPermutation(self, n: int) -> int:
        
        mod = 10**9 + 7
        
        class Vowel(IntEnum):
            A = 0
            E = 1
            I = 2
            O = 3
            U = 4
        
        nstrs = [1] * 5
        
        while n > 1:
            (a, e, i, o, u) = nstrs
            nstrs[Vowel.A] = e
            nstrs[Vowel.E] = a + i  
            nstrs[Vowel.I] = a + e + o + u  
            nstrs[Vowel.O] = i + u
            nstrs[Vowel.U] = a 
            
            n -= 1
        
        return sum(nstrs) % mod

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        a=e=i=o=u=1
        if n==0:
            return 0
        for z in range(n-1):
            a,e,i,o,u = e,a+i,a+e+o+u,i+u,a
        return (a+e+i+o+u)%1000000007

from collections import defaultdict as dt
class Solution:
    def countVowelPermutation(self, n: int) -> int:
        di={'a':1,'e':1,'i':1,'o':1,'u':1}
        for j in range(1,n):
            e={}
            for i in 'aeiou':
                if i=='e':
                    e[i]= di['a']+di['i']
                elif i=='a':
                    e[i]= di['e']
                elif i=='i':
                    e[i]=di['a']+di['e']+di['o']+di['u']
                elif i=='o':
                    e[i]=di['i']+di['u']
                else:
                    e[i]=di['a']
            di=e
        return sum(list(di.values()))%(10**9+7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        mod = 10 ** 9 + 7
        dp = [1] * 5
        for _ in range(n - 1):
            add = [0] * 5
            # from a
            add[1] = (add[1] + dp[0]) % mod
            # from e
            add[0] = (add[0] + dp[1]) % mod
            add[2] = (add[2] + dp[1]) % mod
            # from i
            add[0] = (add[0] + dp[2]) % mod
            add[1] = (add[1] + dp[2]) % mod
            add[3] = (add[3] + dp[2]) % mod
            add[4] = (add[4] + dp[2]) % mod
            # from o
            add[2] = (add[2] + dp[3]) % mod
            add[4] = (add[4] + dp[3]) % mod
            # from u
            add[0] = (add[0] + dp[4]) % mod
            for i in range(5):
                dp[i] = add[i] % mod
        return sum(dp) % mod

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        from collections import defaultdict
        
        end = dict()
        end['a'] = 1
        end['e'] = 1
        end['i'] = 1
        end['o'] = 1
        end['u'] = 1
                        
        for j in range(n-1):
            
            for_a = end['e'] + end['i'] + end['u']
            for_e = end['a'] + end['i']
            for_i = end['e'] + end['o']
            for_o = end['i']
            for_u = end['o'] + end['i']

            end['a'] = for_a
            end['e'] = for_e
            end['i'] = for_i
            end['o'] = for_o
            end['u'] = for_u
                        
        count = sum([v for k, v in list(end.items())])
        
        return count % (10**9 + 7)       



class Solution:
    def countVowelPermutation(self, n: int) -> int:
        mod = 10**9 + 7
        d = {
            0: (1,),
            1: (0, 2),
            2: (0, 1, 3, 4),
            3: (2, 4),
            4: (0,)
        }
        a0 = [1] * 5
        for i in range(n - 1):
            a1 = [0] * 5
            for j in range(5):
                for k in d[j]:
                    a1[k] = (a1[k] + a0[j]) % mod
            a0 = a1
        return sum(a0) % mod

class Solution:
    def countVowelPermutation(self, n: int) -> int:  
        # a -> e
        # e -> a,i
        # i -> a,e,o,u
        # o -> i,u
        # u -> a
        rules = [[1,2,4],[0,2],[1,3],[2],[2,3]]
        dp = [1]*5
        
        for i in range(1,n):
            dp_new = [0]*5
            for j in range(5):
                for k in rules[j]:
                    dp_new[j] += dp[k]%(10**9+7)
            dp = dp_new
            
        return sum(dp)%(10**9+7)
        



class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = [[1]*5 for _ in range(n)]
        
        for i in range(1, n):
            dp[i][0] = dp[i-1][1]
            dp[i][1] = dp[i-1][0] + dp[i-1][2]
            dp[i][2] = dp[i-1][0] + dp[i-1][1] + dp[i-1][3] + dp[i-1][4]
            dp[i][3] = dp[i-1][2] + dp[i-1][4]
            dp[i][4] = dp[i-1][0]
        
        return sum(dp[n-1]) % (10**9 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        if n == 1:
            return 5
        a, e, o, u, i = 1, 1, 1, 1, 1
        for _ in range(1, n):
            a, e, o, u, i = e + u + i, i + a, i, i + o, e + o
        return (a + e + o + u + i) % (10**9 + 7)


mod_ = 10**9+7

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = [[0 for char in range(5)] for t in range(n)]
        dp[0] = [1 for char in range(5)]
        for i in range(1,n):
            dp[i][0] = (dp[i][0]+dp[i-1][1] + dp[i-1][2] + dp[i-1][4]) % mod_
            dp[i][1] = (dp[i][1]+dp[i-1][0] + dp[i-1][2]) % mod_
            dp[i][2] = (dp[i][2]+dp[i-1][1] + dp[i-1][3]) % mod_ 
            dp[i][3] = (dp[i][3]+dp[i-1][2]) % mod_ 
            dp[i][4] = (dp[i][4] + dp[i-1][2] + dp[i-1][3]) % mod_
            
        return sum(dp[-1]) % mod_

class Solution:
    def countVowelPermutation(self, n: int) -> int:
          mod = 10**9 + 7
          count={'a':1,'e':1,'i':1,'o':1,'u':1}
          dic={'a':['e'],'e':['a','i'],'i':['a','e','o','u'],'o':['i','u'],'u':['a']}

          for i in range (n-1):
              tmp = {}
              for x in dic:
                for v in dic[x]:
                  tmp[v] = (tmp.get(v,0) + count[x])%mod
              count = tmp
          return sum(count.values())%mod


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        if n == 1 :
            return 5
        
        T = {
            'a': ['e'],
            'e': ['a', 'i'],
            'i': ['a', 'e', 'o', 'u'],
            'o': ['i', 'u'],
            'u': ['a']
        }
        
        dp = {l: [0 for i in range(n)] for l in 'aeiou'}
        for letter in 'aeiou':
            dp[letter][1] = len(T[letter])
        
        
        for i in range(2, n):
            for l in 'aeiou':
                total = 0
                for r in T[l]:
                    total += dp[r][i-1] % 1000000007
                dp[l][i] = total
        
        return sum(dp[letter][n-1] for letter in 'aeiou') % 1000000007

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = {'a':1, 'e':1, 'i':1, 'o':1, 'u':1}
        follows = {'a':'e', 'e':'ai', 'i':'aeou', 'o':'iu', 'u':'a'}
        mod = 10**9+7
        for _ in range(1, n):
            dp2 = {}
            for c, v in dp.items():
                for f in follows[c]:
                    dp2[f] = (dp2.get(f, 0)+v)%mod
                
            dp = dp2
        return sum(dp.values())%mod

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        res=[[0 for i in range(5)]
             for j in range(n)]
        result=0
        if n==1:
            return 5
        for i in range(5):
            res[0][i]=1
        for i in range(1,n):
            res[i][0]=(res[i-1][1]+res[i-1][2]+res[i-1][4])
            res[i][1]=(res[i-1][0]+res[i-1][2])
            res[i][2]=(res[i-1][1]+res[i-1][3])
            res[i][3]=(res[i-1][2])
            res[i][4]=(res[i-1][2]+res[i-1][3])
        for i in range(5):
            result=(result+res[n-1][i])%1000000007
        return result


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        m = 10**9+7
        a=e=i=o=u=1
        for _ in range(n-1):
            a,e,i,o,u = (e+i+u)%m,(a+i)%m,(e+o)%m,i%m,(i+o)%m
        return (a+e+i+o+u)%m


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp_array = [[0] * 5 for _ in range(n + 1)]
        dp_array[1] = [1, 1, 1, 1, 1]
        for i in range(2, n + 1):
            # a is allowed to follow e, i, or u.
            dp_array[i][0] = dp_array[i - 1][1] + dp_array[i - 1][2] + dp_array[i - 1][4]
            # e is allowed to follow a or i.
            dp_array[i][1] = dp_array[i - 1][0] +  dp_array[i - 1][2]
            # i is allowed to follow e or o.
            dp_array[i][2] = dp_array[i - 1][1] + dp_array[i - 1][3]
            # o is allowed to follow i
            dp_array[i][3] = dp_array[i - 1][2]
            # u is allowed to follow i or o.
            dp_array[i][4] = dp_array[i - 1][2] + dp_array[i - 1][3]
        return sum(dp_array[n]) % ((10 ** 9) + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        MOD = 10**9+7
        dp = [1]*5
        
        foll = [[1], [0, 2], [0, 1, 3, 4], [2, 4], [0]]
        for _ in range(1, n):
            tmp = [0]*5
            for idx, follow in enumerate(foll):
                for i in follow:
                    tmp[idx] += dp[i]
                    tmp[idx] %= MOD
            dp = tmp
                    
        return sum(dp)%MOD


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = [[0 for j in range(n)] for i in range(5)]
        md = 10**9+7
        for i in range(5):
            dp[i][0] = 1
        # [a, e, i, o, u] => [0, 1, 2, 3, 4]
        A, E, I, O, U = 0, 1, 2, 3, 4
        for i in range(1, n):
            dp[E][i] = (dp[E][i]+dp[A][i-1])%md
            
            dp[A][i] = (dp[A][i]+dp[E][i-1])%md
            dp[I][i] = (dp[I][i]+dp[E][i-1])%md
            
            dp[A][i] = (dp[A][i]+dp[I][i-1])%md
            dp[E][i] = (dp[E][i]+dp[I][i-1])%md
            dp[O][i] = (dp[O][i]+dp[I][i-1])%md
            dp[U][i] = (dp[U][i]+dp[I][i-1])%md
            
            dp[I][i] = (dp[I][i]+dp[O][i-1])%md
            dp[U][i] = (dp[U][i]+dp[O][i-1])%md
            
            dp[A][i] = (dp[A][i]+dp[U][i-1])%md
        ans = 0
        for i in range(5):
            ans = (ans+dp[i][-1])%md
        return ans

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        valid = {
            'a': 'e',
            'e': 'ai',
            'i': 'aeou',
            'o': 'iu',
            'u': 'a',
        }
        
        cmap = {
            'a': 0,
            'e': 1,
            'i': 2,
            'o': 3,
            'u': 4,
        }
        
        last = [1] * 5
        for i in range(n-1):
            nex = [0] * 5
            for j in 'aeiou':
                for k in valid[j]:
                    nex[cmap[k]] += last[cmap[j]] % (10**9+7)
                    # nex[cmap[k]] += last[cmap[j]]
            last = nex
        return sum(last) % (10**9+7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        mod = int(1e9 + 7)

        # graph[0] = 'a' can come after 'e', 'i', 'u'
        # graph[1] = 'e' can come after 'a', 'i'
        # graph[2] = 'i' can come after 'e', 'o'
        # graph[3] = 'o' can come after 'i'
        # graph[4] = 'u' can come after 'i', 'o'
        graph = [[1, 2, 4], [0, 2], [1, 3], [2], [2, 3]]

        # dp[i] = number of ways that ends with letter i
        dp = [1] * 5

        for i in range(n - 1):
            copy = dp[:]
            for j in range(5):
                dp[j] = 0
                for k in graph[j]:
                    dp[j] += copy[k]
                    dp[j] %= mod
        
        ans = 0

        for cnt in dp:
            ans += cnt
            ans %= mod
        
        return ans



class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = [[0 for _ in range(5)] for _ in range(n + 1)]
        for i in range(5):
            dp[n][i] = 1
        
        mod = 10**9 + 7
        for i in range(n - 1, 0, -1):
            for j in range(5):
                if j == 0:
                    dp[i][j] = dp[i + 1][j + 1]
                elif j == 1:
                    dp[i][j] = (dp[i + 1][j - 1] + dp[i + 1][j + 1])%mod
                elif j == 2:
                    dp[i][j] = (dp[i + 1][j - 1] + dp[i + 1][j + 1])%mod
                    dp[i][j] = (dp[i][j] + dp[i + 1][j - 2] + dp[i + 1][j + 2])%mod
                elif j == 3:
                    dp[i][j] = (dp[i + 1][j - 1] + dp[i + 1][j + 1])%mod
                elif j == 4:
                    dp[i][j] = dp[i + 1][0]
        
        # print(dp)
        res = 0
        for j in range(5):
            res = (res + dp[1][j])%mod
        return res

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        from collections import defaultdict
        
        end = dict()
        end['a'] = 1
        end['e'] = 1
        end['i'] = 1
        end['o'] = 1
        end['u'] = 1
                        
        for j in range(n-1):
            
            for_a = end['e'] + end['i'] + end['u']
            for_e = end['a'] + end['i']
            for_i = end['e'] + end['o']
            for_o = end['i']
            for_u = end['o'] + end['i']

            end['a'] = for_a
            end['e'] = for_e
            end['i'] = for_i
            end['o'] = for_o
            end['u'] = for_u
                        
        count = sum([v for k, v in list(end.items())])
        
        return count % (10**9 + 7) 


#leetCode 1220. Count Vowels Permutation
class Solution:
    def countVowelPermutation(self, n):
        last_a, last_e, last_i, last_o, last_u = 1,1,1,1,1
        mod = round(1e9+7)
        for i in range(n-1):
            cur_a = (last_e + last_i + last_u) % mod
            cur_e = (last_a + last_i) % mod
            cur_i = (last_e + last_o) % mod
            cur_o = (last_i) % mod
            cur_u = (last_i + last_o) % mod
            last_a, last_e, last_i, last_o, last_u = cur_a, cur_e, cur_i, cur_o, cur_u
        #注意取整，加在一起可能越界
        return sum([last_a, last_e, last_i, last_o, last_u]) % mod


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = [[0 for _ in range(5)] for _ in range(n+1)]
        for i in range(5):
            dp[1][i] = 1
        for i in range(2,n+1):
            dp[i][0] = dp[i-1][1] + dp[i-1][2] + dp[i-1][4] 
            dp[i][1] = dp[i-1][0] + dp[i-1][2]
            dp[i][2] = dp[i-1][1] + dp[i-1][3]
            dp[i][3] = dp[i-1][2]
            dp[i][4] = dp[i-1][2] + dp[i-1][3]
        return sum(dp[n]) % (1000000000 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = [[1 for _ in range(5)]] + [[0 for _ in range(5)] for _ in range(n-1)]
        
        for i in range(1, n):
            # a = ea + ia + ua
            dp[i][0] = dp[i-1][1] + dp[i-1][2] + dp[i-1][4]
            # e = ae + ie
            dp[i][1] = dp[i-1][0] + dp[i-1][2]
            # i = ei + oi
            dp[i][2] = dp[i-1][1] + dp[i-1][3]
            # o = io
            dp[i][3] = dp[i-1][2]
            # u = iu + ou
            dp[i][4] = dp[i-1][2] + dp[i-1][3]
            
        return sum(dp[-1]) % (10 ** 9 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        M = 10**9+7
        dp = [[0 for j in range(n+1)] for i in range(5)]
        for i in range(5):
            dp[i][1] = 1
            
#         for i in range(5):
#             print(dp[i])
        
        for j in range(2, n+1):
            dp[0][j] = dp[1][j-1]+dp[2][j-1]+dp[4][j-1]
            dp[1][j] = dp[0][j-1]+dp[2][j-1]
            dp[2][j] = dp[1][j-1]+dp[3][j-1]
            dp[3][j] = dp[2][j-1]
            dp[4][j] = dp[2][j-1]+dp[3][j-1]
        
        res = 0
        for i in range(5):
            res += dp[i][n]
        return res%M

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        vowels_idx = {'a' : 0, 'e' : 1, 'i' : 2, 'o' : 3, 'u' : 4}
        f = [None] * n
        f[n-1] = [1] * len(vowels_idx)
        for i in range(n-2, -1, -1):
            f[i] = [0] * len(vowels_idx)
            for vowel in vowels_idx:
                if vowel == 'a':
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['e']]
                elif vowel == 'e':
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['a']] + f[i+1][vowels_idx['i']]
                elif vowel == 'i':
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['a']] + f[i+1][vowels_idx['e']] + f[i+1][vowels_idx['o']] + f[i+1][vowels_idx['u']]
                elif vowel == 'o':
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['i']] + f[i+1][vowels_idx['u']]
                else:
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['a']]
                f[i][vowels_idx[vowel]] %= (10**9 + 7)
        total = 0
        for vowel in vowels_idx:
            total += f[0][vowels_idx[vowel]]
        return total % (10**9 + 7)
            
        memo = {}
        def f(i, prev_vowel):
            if i == n:
                return 1
            
            if (i, prev_vowel) in memo:
                return memo[(i, prev_vowel)]
            
            cnt = 0
            if prev_vowel == 'a':
                cnt += f(i + 1, 'e')
            elif prev_vowel == 'e':
                cnt += f(i + 1, 'a') + f(i + 1, 'i')
            elif prev_vowel == 'i':
                cnt += f(i + 1, 'a') + f(i + 1, 'e') + f(i + 1, 'o') + f(i + 1, 'u')
            elif prev_vowel == 'o':
                cnt += f(i + 1, 'i') + f(i + 1, 'u')
            else:
                cnt += f(i + 1, 'a')
                
            memo[(i, prev_vowel)] = cnt % (10**9 + 7)
            return cnt
        
        cnt = 0
        for vowel in ['a', 'e', 'i', 'o', 'u']:
            cnt += f(1, vowel)
        
        return cnt % (10**9 + 7)



class Solution:
    def countVowelPermutation(self, n: int) -> int:
        vowels_idx = {'a' : 0, 'e' : 1, 'i' : 2, 'o' : 3, 'u' : 4}
        f = [None] * n
        f[n-1] = [1] * len(vowels_idx)
        for i in range(n-2, -1, -1):
            f[i] = [0] * len(vowels_idx)
            for vowel in vowels_idx:
                # If we have some vowel at current index i, then we know it can only
                # be followed by a specific set of vowels, depending on the vowel at i
                if vowel == 'a':
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['e']]
                elif vowel == 'e':
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['a']] + f[i+1][vowels_idx['i']]
                elif vowel == 'i':
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['a']] + f[i+1][vowels_idx['e']] + f[i+1][vowels_idx['o']] + f[i+1][vowels_idx['u']]
                elif vowel == 'o':
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['i']] + f[i+1][vowels_idx['u']]
                else:
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['a']]
                f[i][vowels_idx[vowel]] %= (10**9 + 7)
        total = 0
        for vowel in vowels_idx:
            total += f[0][vowels_idx[vowel]]
        return total % (10**9 + 7)
            
        memo = {}
        def f(i, prev_vowel):
            if i == n:
                return 1
            
            if (i, prev_vowel) in memo:
                return memo[(i, prev_vowel)]
            
            cnt = 0
            if prev_vowel == 'a':
                cnt += f(i + 1, 'e')
            elif prev_vowel == 'e':
                cnt += f(i + 1, 'a') + f(i + 1, 'i')
            elif prev_vowel == 'i':
                cnt += f(i + 1, 'a') + f(i + 1, 'e') + f(i + 1, 'o') + f(i + 1, 'u')
            elif prev_vowel == 'o':
                cnt += f(i + 1, 'i') + f(i + 1, 'u')
            else:
                cnt += f(i + 1, 'a')
                
            memo[(i, prev_vowel)] = cnt % (10**9 + 7)
            return cnt
        
        cnt = 0
        for vowel in ['a', 'e', 'i', 'o', 'u']:
            cnt += f(1, vowel)
        
        return cnt % (10**9 + 7)



class Solution:
    def countVowelPermutation(self, n: int) -> int:
        vowels_idx = {'a' : 0, 'e' : 1, 'i' : 2, 'o' : 3, 'u' : 4}
        f = [None] * n
        # We can safely assume a string can end in any vowel
        f[n-1] = [1] * len(vowels_idx)
        for i in range(n-2, -1, -1):
            f[i] = [0] * len(vowels_idx)
            for vowel in vowels_idx:
                # If we have some vowel at current index i, then we know it can only
                # be followed by a specific set of vowels, depending on the vowel at i
                if vowel == 'a':
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['e']]
                elif vowel == 'e':
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['a']] + f[i+1][vowels_idx['i']]
                elif vowel == 'i':
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['a']] + f[i+1][vowels_idx['e']] + f[i+1][vowels_idx['o']] + f[i+1][vowels_idx['u']]
                elif vowel == 'o':
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['i']] + f[i+1][vowels_idx['u']]
                else:
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['a']]
                f[i][vowels_idx[vowel]] %= (10**9 + 7)
        total = 0
        for vowel in vowels_idx:
            total += f[0][vowels_idx[vowel]]
        return total % (10**9 + 7)
            
        memo = {}
        def f(i, prev_vowel):
            if i == n:
                return 1
            
            if (i, prev_vowel) in memo:
                return memo[(i, prev_vowel)]
            
            cnt = 0
            if prev_vowel == 'a':
                cnt += f(i + 1, 'e')
            elif prev_vowel == 'e':
                cnt += f(i + 1, 'a') + f(i + 1, 'i')
            elif prev_vowel == 'i':
                cnt += f(i + 1, 'a') + f(i + 1, 'e') + f(i + 1, 'o') + f(i + 1, 'u')
            elif prev_vowel == 'o':
                cnt += f(i + 1, 'i') + f(i + 1, 'u')
            else:
                cnt += f(i + 1, 'a')
                
            memo[(i, prev_vowel)] = cnt % (10**9 + 7)
            return cnt
        
        cnt = 0
        for vowel in ['a', 'e', 'i', 'o', 'u']:
            cnt += f(1, vowel)
        
        return cnt % (10**9 + 7)



class Solution:
    def countVowelPermutation(self, n: int) -> int:
        vowels_idx = {'a' : 0, 'e' : 1, 'i' : 2, 'o' : 3, 'u' : 4}
        f = [None] * n
        f[n-1] = [1] * len(vowels_idx)
        for i in range(n-2, -1, -1):
            f[i] = [0] * len(vowels_idx)
            for vowel in vowels_idx:
                if vowel == 'a':
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['e']]
                elif vowel == 'e':
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['a']] + f[i+1][vowels_idx['i']]
                elif vowel == 'i':
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['a']] + f[i+1][vowels_idx['e']] + f[i+1][vowels_idx['o']] + f[i+1][vowels_idx['u']]
                elif vowel == 'o':
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['i']] + f[i+1][vowels_idx['u']]
                else:
                    f[i][vowels_idx[vowel]] += f[i+1][vowels_idx['a']]
                f[i][vowels_idx[vowel]] %= (10**9 + 7)
        total = 0
        for vowel in vowels_idx:
            total += f[0][vowels_idx[vowel]]
        return total % (10**9 + 7)

                                        
            
        memo = {}
        def f(i, prev_vowel):
            if i == n:
                return 1
            
            if (i, prev_vowel) in memo:
                return memo[(i, prev_vowel)]
            
            cnt = 0
            if prev_vowel == 'a':
                cnt += f(i + 1, 'e')
            elif prev_vowel == 'e':
                cnt += f(i + 1, 'a') + f(i + 1, 'i')
            elif prev_vowel == 'i':
                cnt += f(i + 1, 'a') + f(i + 1, 'e') + f(i + 1, 'o') + f(i + 1, 'u')
            elif prev_vowel == 'o':
                cnt += f(i + 1, 'i') + f(i + 1, 'u')
            else:
                cnt += f(i + 1, 'a')
                
            memo[(i, prev_vowel)] = cnt % (10**9 + 7)
            return cnt
        
        cnt = 0
        for vowel in ['a', 'e', 'i', 'o', 'u']:
            cnt += f(1, vowel)
        
        return cnt % (10**9 + 7)



class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = {}
        for c in ['a', 'e', 'i', 'o', 'u']:
            dp[c] = 1
        sources = {}
        sources['a'] = ['e','i','u']
        sources['e'] = ['a', 'i']
        sources['i'] = ['e', 'o']
        sources['o'] = ['i']
        sources['u'] = ['i', 'o']
        for i in range(2, n+1):
            next_dp = {}
            for c in ['a', 'e', 'i', 'o', 'u']:
                next_dp[c] = sum(
                    dp[s] for s in sources[c]
                ) % 1000000007
            dp = next_dp
        return sum(dp.values())  % 1000000007


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        
        from collections import defaultdict
        
        end = dict()
        end['a'] = 1
        end['e'] = 1
        end['i'] = 1
        end['o'] = 1
        end['u'] = 1
                        
        for j in range(n-1):
            
            for_a = end['e'] + end['i'] + end['u']
            for_e = end['a'] + end['i']
            for_i = end['e'] + end['o']
            for_o = end['i']
            for_u = end['o'] + end['i']

            end['a'] = for_a
            end['e'] = for_e
            end['i'] = for_i
            end['o'] = for_o
            end['u'] = for_u
                        
        count = sum([v for k, v in end.items()])
        
        return count % (10**9 + 7)       

class Solution:
    def countVowelPermutation(self, n: int) -> int:

        graph = {
            0: (1,),
            1: (0, 2),
            2: (0, 1, 3, 4),
            3: (2, 4),
            4: (0,),
        }

        permutations = [1] * 5
        for _ in range(n - 1):
            next_permutations = [0] * 5
            for node in range(5):
                for neighbour in graph[node]:
                    next_permutations[neighbour] += permutations[node]
            permutations = next_permutations

        return sum(permutations) % (10 ** 9 + 7)

import numpy as np
class Solution:
    def countVowelPermutation(self, n: int) -> int:
        mod = 10**9 + 7
        if n == 1:
            return 5
        M = np.matrix([[0,1,0,0,0],[1,0,1,0,0],[1,1,0,1,1],[0,0,1,0,1],[1,0,0,0,0]])
        print(M)
        res = 1
        N = n-1 # times of permutation
        while N > 0:
            if N%2:
                res = res * M %mod
                print(res)
                                
            M = M*M%mod   # speed up         
            N//= 2
           
        return int(np.sum(res))%mod


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        '''
        
        '''
        g = {
            'a':['e'],
            'e':['a','i'],
            'i':['a','e','o','u'],
            'o':['i','u'],
            'u':['a']
        }
        d2i = {
            'a':0,
            'e':1,
            'i':2,
            'o':3,
            'u':4
        }
        newg = {}
        for k,v in g.items():
            newg[d2i[k]] = [d2i[letter] for letter in v]

        mod = 10**9 + 7
        prev = [1]*5

        for _ in range(n-1):
            dp = [None]*5
            for i in range(5):
                dp[i] = sum(prev[j] for j in newg[i])%mod
            prev = dp
        return sum(prev)%mod

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        m = {0: [1], 1: [0, 2], 2: [0, 1, 3, 4], 3: [2, 4], 4: [0]}
        dp = [1] * 5         
        for i in range(1, n):
            dp2 = [0] * 5
            for j in range(5):                
                for k in m[j]: dp2[k] += dp[j]
            dp = dp2
        return sum(dp) % (10**9+7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        result = [1]*5
        graph = [[1],[0,2],[0,1,3,4],[2,4],[0]]
        for count in range(1,n):
            tempResult = [0]*5
            for i in range(5):
                for j in graph[i]:
                    tempResult[j]+=result[i]
            result = tempResult
        return sum(result)%(10**9+7)

class Solution:

    def countVowelPermutation(self, n: int) -> int:
        prevfreq = {'a':1, 'e':1, 'o':1, 'i':1, 'u':1}
        vmap = {'a':['e'], 'e':['a','i'], 'i':['a','e','o','u'], 'o':['i','u'], 'u':['a']}
        for i in range(1, n):
            curfreq = defaultdict(int)
            for v, freq in prevfreq.items():
                for nextv in vmap[v]:
                    curfreq[nextv] += freq
            prevfreq = curfreq
        return sum(prevfreq.values()) % (10**9+7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        valid = {
            'a': 'e',
            'e': 'ai',
            'i': 'aeou',
            'o': 'iu',
            'u': 'a',
        }
        
        cmap = {
            'a': 0,
            'e': 1,
            'i': 2,
            'o': 3,
            'u': 4,
        }
        
        last = [1] * 5
        for i in range(n-1):
            nex = [0] * 5
            for j in 'aeiou':
                for k in valid[j]:
                    # nex[cmap[k]] += last[cmap[j]] % (10**9+7)
                    nex[cmap[k]] += last[cmap[j]]
            last = nex
        return sum(last) % (10**9+7)

# https://leetcode.com/problems/count-vowels-permutation/discuss/398286/Simple-Python-(With-Diagram)

class Solution:

    def countVowelPermutation(self, n: int) -> int:
        prevfreq = {'a':1, 'e':1, 'o':1, 'i':1, 'u':1}
        vmap = {'a':['e'], 'e':['a','i'], 'i':['a','e','o','u'], 'o':['i','u'], 'u':['a']}
        for i in range(1, n):
            curfreq = defaultdict(int)
            for v, freq in prevfreq.items():
                for nextv in vmap[v]:
                    curfreq[nextv] += freq
            prevfreq = curfreq
        return sum(prevfreq.values()) % (10**9+7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = [1] * 5
        mod = 10**9 + 7
        for i in range(1, n):
            dp[0],dp[1],dp[2],dp[3],dp[4]=(dp[1]+dp[2]+dp[4])%mod,(dp[0]+dp[2])%mod,(dp[1]+dp[3])%mod, dp[2], (dp[2]+dp[3])%mod
        
        return sum(dp)%mod

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp=[[0,0,0,0,0] for i in range(n)]
        dp[0]=[1,1,1,1,1]
        for m in range(1,n):
            dp[m][0]=dp[m-1][1]+dp[m-1][2]+dp[m-1][4]
            dp[m][1]=dp[m-1][0]+dp[m-1][2]
            dp[m][2]=dp[m-1][1]+dp[m-1][3]
            dp[m][3]=dp[m-1][2]
            dp[m][4]=dp[m-1][2]+dp[m-1][3]
        return sum(dp[-1])%(pow(10,9)+7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        prevfreq = {'a':1, 'e':1, 'o':1, 'i':1, 'u':1}
        vmap = {'a':['e'], 'e':['a','i'], 'i':['a','e','o','u'], 'o':['i','u'], 'u':['a']}
        for i in range(1, n):
            # print(i)
            curfreq = defaultdict(int)
            for v, freq in prevfreq.items():
                # print(v,freq)
                for nextv in vmap[v]:
                    curfreq[nextv] += freq
                    # print(curfreq)
            prevfreq = curfreq
        return sum(prevfreq.values()) % (10**9+7)

class Solution:
    @lru_cache(None)
    def countVowelPermutation(self, n: int) -> int:
        prevs = {'a':1, 'e':1, 'i':1, 'o':1, 'u':1}
        for i in range(1, n):
            cur = defaultdict(int)
            for prev, count in prevs.items():
                if prev == 'a':
                    cur['e'] += count
                elif prev == 'e':
                    for nextch in ['a', 'i']:
                        cur[nextch] += count
                elif prev == 'i':
                    for nextch in ['a', 'e', 'o', 'u']:
                        cur[nextch] += count 
                elif prev == 'o':
                    for nextch in ['i', 'u']:
                        cur[nextch] += count
                elif prev == 'u':
                    cur['a'] += count
            prevs = cur
        return sum(prevs.values()) % 1000000007
        '''
        vocals = ['aeiou']
        arr = vocals * n
        prods = list(map(\"\".join, itertools.product(*arr)))
        count = 0
        for prod in prods:
            if \"aa\" in prod or \"ai\" in prod or \"ao\" in prod or \"au\" in prod or \"ee\" in prod or \"eo\" in prod or \"eu\" in prod or \"ii\" in prod or \"oa\" in prod or \"oe\" in prod or \"oo\" in prod or \"ue\" in prod or \"ui\" in prod or \"uo\" in prod or \"uu\" in prod:
                continue
            print(prod)
            count += 1
        return count%(10**9+7)
        '''

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        prevs = {'a':1, 'e':1, 'i':1, 'o':1, 'u':1}
        for i in range(1, n):
            cur = defaultdict(int)
            for prev, count in prevs.items():
                if prev == 'a':
                    cur['e'] += count
                elif prev == 'e':
                    for nextch in ['a', 'i']:
                        cur[nextch] += count
                elif prev == 'i':
                    for nextch in ['a', 'e', 'o', 'u']:
                        cur[nextch] += count 
                elif prev == 'o':
                    for nextch in ['i', 'u']:
                        cur[nextch] += count
                elif prev == 'u':
                    cur['a'] += count
            prevs = cur
        return sum(prevs.values()) % 1000000007

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = dict.fromkeys(('a', 'e', 'i', 'o', 'u'), 1)
        for k in range(1, n):
            dp = {
                'a': sum(dp[v] for v in ('e', 'i', 'u')),
                'e': sum(dp[v] for v in ('a', 'i')),
                'i': sum(dp[v] for v in ('e', 'o')),
                'o': dp['i'],
                'u': sum(dp[v] for v in ('i', 'o'))
            }
        return sum(dp.values()) % (10 ** 9 + 7)

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        dp = {}
        dp[1] = {}
        for c in ['a', 'e', 'i', 'o', 'u']:
            dp[1][c] = 1
        sources = {}
        sources['a'] = ['e','i','u']
        sources['e'] = ['a', 'i']
        sources['i'] = ['e', 'o']
        sources['o'] = ['i']
        sources['u'] = ['i', 'o']
        for i in range(2, n+1):
            dp[i] = {}
            for c in ['a', 'e', 'i', 'o', 'u']:
                dp[i][c] = sum(
                    dp[i-1][s] for s in sources[c]
                ) % 1000000007
        return sum(dp[n][c] for c in dp[n])  % 1000000007


class Solution:
    def countVowelPermutation(self, n: int) -> int:
        if not n:
            return 0

        dic = {
            'a': ['e'],
            'e': ['a', 'i'],
            'i': ['a', 'e', 'o', 'u'],
            'o': ['i', 'u'],
            'u': ['a']
        }

        dp_cur = {
            'a': 1,
            'e': 1,
            'i': 1,
            'o': 1,
            'u': 1,
        }

        for i in range(1, n):
            dp_next = collections.defaultdict(int)
            for key, item in list(dp_cur.items()):
                for j in dic[key]:
                    dp_next[j] += item
            dp_cur = dp_next

        return sum(dp_cur.values()) % (10 ** 9 + 7)