Description
Given integer n, count strings of length n consisting only of vowels (a, e, i, o, u) that follow specific transition rules between consecutive characters. Return the result as an integer.
Examples
Input:
n = 1Output:
5Explanation:
Length 1: each vowel forms a valid string. 5 vowels = 5 strings: a, e, i, o, u.
Input:
n = 3Output:
19Explanation:
Following vowel transition rules (a→e, e→a/i, i→a/e/o/u, o→i/u, u→a), there are 19 valid strings of length 3.
Input:
n = 4Output:
35Explanation:
Matrix exponentiation or iterative DP for n=4. Transition graph sums to 35 valid length-4 strings.
Constraints
- •
1 ≤ n ≤ 2 × 10⁴