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

Source: leetcode | Difficulty: MEDIUM
Tags: Dynamic programming

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 = 1000000000.0 + 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 = 1000000000.0 + 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 = 1000000000.0 + 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 + 1000000000.0

		@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
			elif 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):
			(e, a, i, o, u) = ((a + i) % p, (e + i + u) % p, (e + o) % p, i % p, (i + o) % p)
			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)


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:

	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]}
		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
		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], 1: [0, 2], 2: [0, 1, 3, 4], 3: [2, 4], 4: [0]}
		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:
				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:
		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)


MOD = int(1000000000.0 + 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:
		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)


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:
		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(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:
		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:
		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)


class Solution:

	def countVowelPermutation(self, n: int) -> int:
		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):
			current_count = [0] * 5
			current_count[0] = prev_count[1]
			current_count[1] = prev_count[0] + prev_count[2]
			current_count[2] = prev_count[0] + prev_count[1] + prev_count[3] + prev_count[4]
			current_count[3] = prev_count[2] + prev_count[4]
			current_count[4] = prev_count[0]
			prev_count = current_count
		return sum(current_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:
		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:
		mod = 10 ** 9 + 7
		count = 0
		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
			add[1] = (add[1] + dp[0]) % mod
			add[0] = (add[0] + dp[1]) % mod
			add[2] = (add[2] + dp[1]) % mod
			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
			add[2] = (add[2] + dp[3]) % mod
			add[4] = (add[4] + dp[3]) % mod
			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:
		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:
		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)


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:
		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)
		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)
			last = nex
		return sum(last) % (10 ** 9 + 7)


class Solution:

	def countVowelPermutation(self, n: int) -> int:
		mod = int(1000000000.0 + 7)
		graph = [[1, 2, 4], [0, 2], [1, 3], [2], [2, 3]]
		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]
		res = 0
		for j in range(5):
			res = (res + dp[1][j]) % mod
		return res


class Solution:

	def countVowelPermutation(self, n):
		(last_a, last_e, last_i, last_o, last_u) = (1, 1, 1, 1, 1)
		mod = round(1000000000.0 + 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:
		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:
		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
		while N > 0:
			if N % 2:
				res = res * M % mod
				print(res)
			M = M * M % mod
			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:
		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:
		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:

	@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


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)