## Algorithm

Problem Name: 1220. Count Vowels Permutation

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`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public int countVowelPermutation(int n) {
long aCount = 1;
long eCount = 1;
long iCount = 1;
long oCount = 1;
long uCount = 1;
final int MOD = 1000000007;
for (int i = 1; i  <  n; i++) {
long aCountNew = (eCount + iCount + uCount) % MOD;
long eCountNew = (aCount + iCount) % MOD;
long iCountNew = (eCount + oCount) % MOD;
long oCountNew = (iCount) % MOD;
long uCountNew = (iCount + oCount) % MOD;
aCount = aCountNew;
eCount = eCountNew;
iCount = iCountNew;
oCount = oCountNew;
uCount = uCountNew;
}
long result = (aCount + eCount + iCount + oCount + uCount) % MOD;
return (int) result;
}
}
``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
5

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const countVowelPermutation = function (n) {
const mod = 1e9 + 7
const arr = [
[0, 1, 1], // a -> e
[0, 1, 2], // e -> a, i
[0, 1, 4], // i -> a, e, o, u
[0, 1, 2], // o -> i, u
[0, 1, 1], // u -> a
]
for (let i = 3; i  < = n; i++) {
arr[0][i % 3] = arr[1][(i - 1) % 3] % mod
arr[1][i % 3] = (arr[0][(i - 1) % 3] + arr[2][(i - 1) % 3]) % mod
arr[2][i % 3] =
(arr[0][(i - 1) % 3] +
arr[1][(i - 1) % 3] +
arr[3][(i - 1) % 3] +
arr[4][(i - 1) % 3]) %
mod
arr[3][i % 3] = (arr[2][(i - 1) % 3] + arr[4][(i - 1) % 3]) % mod
arr[4][i % 3] = arr[0][(i - 1) % 3] % mod
}
return arr.reduce((sum, subArr) => sum + subArr[n % 3], 0) % mod
}
``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
5

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def countVowelPermutation(self, n: int) -> int:
mod = 10 ** 9 + 7
dp = [1] * 5
for _ in range(n - 1):
# from a
# from e
# from i
# from o
# from u
for i in range(5):
return sum(dp) % mod
``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
5