Count Vowels Permutation

Count the length-n strings made from the lowercase vowels a, e, i, o, and u that satisfy these rules for consecutive characters:

• After a, only e is allowed.
• After e, only a or i is allowed.
• After i, any vowel except i is allowed.
• After o, only i or u is allowed.
• After u, only a is allowed.

Any vowel may be the first character. Return the number of valid strings modulo 1000000007.

Example 1:

Input: n = 1

Output: 5

Explanation: Each of the five vowels forms a valid one-character string, since there is no following character to restrict.

Example 2:

Input: n = 2

Output: 10

Explanation: The possible second characters contribute 1 option after a, 2 after e, 4 after i, 2 after o, and 1 after u. Thus there are 1 + 2 + 4 + 2 + 1 = 10 strings.

Example 3:

Input: n = 3

Output: 19

Explanation: Among valid three-character strings, 6 end in a, 5 in e, 3 in i, 2 in o, and 3 in u. These disjoint groups total 19 strings.

Constraints:

• 1 <= n <= 20000