Vowel Chains

Hard

Strings are built only from the lowercase vowels a, e, i, o and u, and each vowel has its own rule about what may come right after it: - after a, only e; - after e, either a or i; - after i, any vowel except i; - after o, either i or u; - after u, only a. Count the strings of length length that follow all the rules. The answer can be large, so return it modulo 10⁹ + 7.

Example 1

length=1 → 5

Each of the five vowels on its own is a valid string.

Example 2

length=2 → 10

"ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua": 10 strings.

Example 3

length=3 → 19

Constraints

1 ≤ length ≤ 2 · 10⁴

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Dynamic Programming

Similar problems

Pattern With Dot and Star Hard Longest Balanced Bracket Stretch Hard Water Between Walls Hard Does the Text Fit the Pattern Hard Biggest Solid Panel Block Hard

Input

length=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 28 tests on the server, hidden ones included.