Problem Statement

Given a positive integer n, return the number of strings of length n can be formed by following rules:

• Each character of the string should be only a lowercase vowel ('a', 'e', 'i', 'o', 'u').
• The vowel 'a' is only allowed to be followed by the vowel 'e'.
• The vowel 'e' can be followed by either 'a' or 'i'.
• The vowel 'i' cannot be followed by another 'i'.
• The vowel 'o' can be followed by either 'i' or 'u'.
• The vowel 'u' must be followed by 'a'.

Return the answer modulo 10^9 + 7, as it could be very large.

Examples

Example 1:

• Input: n = 1
• Expected Output: 5
• Justification: There's only one position, and each vowel can occupy it without restrictions, resulting in 5 possible strings: 'a', 'e', 'i', 'o', 'u'.

Example 2:

• Input: n = 2
• Expected Output: 10
• Justification: Two-character strings following the rules give us ten possibilities: 'ae', 'ea', 'ei', 'ia', 'ie', 'io', 'iu', 'oi', 'ou', 'ua'.

Example 3:

• Input: n = 4
• Expected Output: 35
• Justification: For strings of length 4, following the succession rules strictly, there are 35 valid combinations.

Try it yourself

Try solving this question here: