<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: 

        # allowed = {
        #     'a' : ['e'],
        #     'e' : ['a','i'],
        #     'i' : ['a','e','o','u'],
        #     'o' : ['i','u'],
        #     'u' : ['a']
        # }

        mod = 10 ** 9 + 7

        # @cache
        # def helper(prev,index):

        #     if index  == n:
        #         return 1
        #     ans = 0
        #     for char in allowed[prev]:
        #         ans += helper(char,index+1)
        #     return ans
        # ans = 0
        # for char in allowed.keys():
        #     ans += helper(char,1)
        # return ans % mod

        # base cases
        # index >= n ; return 1 
        # states are prev and index 
        dp = [ [ 0 for i in range(5) ] for i in range(n) ]
        dp[-1][0] = 1
        dp[-1][1] = 1
        dp[-1][2] = 1
        dp[-1][3] = 1
        dp[-1][4] = 1

        allowed = {
            0 : [1],
            1 : [0,2],
            2 : [0,1,3,4],
            3 : [2,4],
            4 : [0]
        }

        for index in range( n - 2 , -1 , -1 ):
            for prev in range(5):
                for char in allowed[prev]:
                    dp[index][prev] += dp[index+1][char]
        # print(dp)
        return sum(dp[0]) % mod

144002