Count Parity-Constrained Vowel Strings

You are given an integer n. A string of length n qualifies if it satisfies all of the following:

• every character is a vowel: a, e, i, o or u;
• the characters are in non-decreasing alphabetical order (a $\leq$ e $\leq$ i $\leq$ o $\leq$ u);
• each of a, i and u appears an odd number of times, or not at all;
• each of e and o appears an even number of times (zero is allowed).

Return the number of qualifying strings. The answer fits in a 64-bit integer.

Examples

Example 1

Input: n = 1
Output: 3
Explanation: "a", "i" and "u". A single "e" or "o" would appear an odd number of times, which is not allowed for those letters.

Example 2

Input: n = 2
Output: 5
Explanation: "ee", "oo", "ai", "au" and "iu". For example "aa" is invalid because a appears twice (even and nonzero), and "ae" is invalid because e appears once.

Example 3

Input: n = 3
Output: 10
Explanation: "aaa", "iii", "uuu", "aiu", "aee", "eei", "eeu", "aoo", "ioo" and "oou".