1220. Count Vowels Permutations

Count the strings of length n made only of vowels (a, e, i, o, u) that obey these rules: 'a' may only be followed by 'e'; 'e' may only be followed by 'a' or 'i'; 'i' may not be followed by another 'i'; 'o' may only be followed by 'i' or 'u'; and 'u' may only be followed by 'a'. Return the count modulo 1000000007. The input is JSON {n}.

Input: JSON {n}.

Output: Integer — the number of valid strings modulo 1e9+7.

Examples

Input: {"n":1}
Output: 5
Explanation: Each single vowel.

Input: {"n":2}
Output: 10
Explanation: Ten valid two-letter strings.

Input: {"n":5}
Output: 68
Explanation: Sixty-eight valid strings.

Constraints

• 1<=n<=2*10^4

Asked by