Description
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
Solution
Python3
class Solution:
def countVowelPermutation(self, n: int) -> int:
a = e = i = o = u = 1
MOD = 10 ** 9 + 7
for _ in range(n - 1):
a, e, i, o, u = e, a + i, a + e + o + u, i + u, a
a %= MOD
e %= MOD
i %= MOD
o %= MOD
u %= MOD
return (a + e + i + o + u) % MOD