<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 {
    unordered_map<char, vector<char>> nextChar;
    unordered_map<char, int> charMap;
    int MOD = 1e9+7;

    vector<vector<int>> dp;

public:
    Solution(){
        charMap['a'] = 0;
        charMap['e'] = 1;
        charMap['i'] = 2;
        charMap['o'] = 3;
        charMap['u'] = 4;


        nextChar['a'].push_back('e');

        nextChar['e'].push_back('a');
        nextChar['e'].push_back('i');

        nextChar['i'].push_back('a');
        nextChar['i'].push_back('e');
        nextChar['i'].push_back('o');
        nextChar['i'].push_back('u');

        nextChar['o'].push_back('i');
        nextChar['o'].push_back('u');

        nextChar['u'].push_back('a');
    }

    int countVowelPermutation(int n) {
        int count = 0;
        dp.resize(n, vector<int>(5, -1));

        for(auto &item: charMap)
        {
            char ch = item.first;
            count += solve(n-1, ch);
            count %= MOD;
        }
        return count;
    }

    int solve(int len, char &ch)
    {
        if(len<=0)
            return 1;
        
        int charInd = charMap[ch];
        if(dp[len][charInd]!=-1)
            return dp[len][charInd];

        int count = 0;

        for(auto &next: nextChar[ch])
        {
            count += solve(len-1, next);
            count %= MOD;
        }
        return dp[len][charInd]=count;
    }
};
44230