<p>Given an integer <code>n</code>, your task is to count how many strings of length <code>n</code> can be formed under the following rules:</p>

<ul>
	<li>Each character is a lower case vowel&nbsp;(<code>&#39;a&#39;</code>, <code>&#39;e&#39;</code>, <code>&#39;i&#39;</code>, <code>&#39;o&#39;</code>, <code>&#39;u&#39;</code>)</li>
	<li>Each vowel&nbsp;<code>&#39;a&#39;</code> may only be followed by an <code>&#39;e&#39;</code>.</li>
	<li>Each vowel&nbsp;<code>&#39;e&#39;</code> may only be followed by an <code>&#39;a&#39;</code>&nbsp;or an <code>&#39;i&#39;</code>.</li>
	<li>Each vowel&nbsp;<code>&#39;i&#39;</code> <strong>may not</strong> be followed by another <code>&#39;i&#39;</code>.</li>
	<li>Each vowel&nbsp;<code>&#39;o&#39;</code> may only be followed by an <code>&#39;i&#39;</code> or a&nbsp;<code>&#39;u&#39;</code>.</li>
	<li>Each vowel&nbsp;<code>&#39;u&#39;</code> may only be followed by an <code>&#39;a&#39;</code>.</li>
</ul>

<p>Since the answer&nbsp;may be too large,&nbsp;return it modulo&nbsp;<code>10^9 + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 1
<strong>Output:</strong> 5
<strong>Explanation:</strong> All possible strings are: &quot;a&quot;, &quot;e&quot;, &quot;i&quot; , &quot;o&quot; and &quot;u&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 2
<strong>Output:</strong> 10
<strong>Explanation:</strong> All possible strings are: &quot;ae&quot;, &quot;ea&quot;, &quot;ei&quot;, &quot;ia&quot;, &quot;ie&quot;, &quot;io&quot;, &quot;iu&quot;, &quot;oi&quot;, &quot;ou&quot; and &quot;ua&quot;.
</pre>

<p><strong class="example">Example 3:&nbsp;</strong></p>

<pre>
<strong>Input:</strong> n = 5
<strong>Output:</strong> 68</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= n &lt;= 2 * 10^4</code></li>
</ul>

class Solution:
    def countVowelPermutation(self, n: int) -> int:
        d = {
            'start' : ['a','e','i','o','u'],
            'a' : ['e'],
            'e' : ['a','i'],
            'i' : ['a','e','o','u'],
            'o' : ['i','u'],
            'u' : ['a']
        }
        
        @functools.lru_cache(None)
        def helper(pre_c, my_n):
            if my_n == n: return 1
            res = 0
            for c in d[pre_c]:
                res += helper(c, my_n+1)
            return res
        return helper('start', 0) % (10**9 + 7)

        # nxt_d = {
        #     0 : ['e'],
        #     1 : ['a','i'],
        #     2 : ['a','e','o','u'],
        #     3 : ['i','u'],
        #     4 : ['a']
        # }

        # c_to_i_d = {
        #     'a' : 0,
        #     'e' : 1,
        #     'i' : 2,
        #     'o' : 3,
        #     'u' : 4
        # }
        
        # cache = [1]*5
        # for _ in range(n-1):
        #     tmp = [0]*5
        #     for i in range(5):
        #         for c in nxt_d[i]:
        #             tmp[c_to_i_d[c]] += cache[i]
        #     cache = tmp
        # return sum(cache) % (10**9 + 7)
                

                
       
189782