<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 {
public: 
    vector<char> lst = {'a', 'e', 'i', 'o', 'u'};

    bool okA(char c){
        return c == 'e';
    }

    bool okE(char c){
        return c == 'a' || c == 'i';
    }

    bool okI(char c){
        return c != 'i';
    }

    bool okO(char c){
        return c == 'u' || c == 'i';
    }
    bool okU(char c){
        return c == 'a';
    }
    
    int mod = 1e9 + 7;
    vector<vector<int>> dp;

    int f(int n, char pr){
        if(n == 0) return dp[n][pr - 'a'] = 1;
        if(dp[n][pr - 'a'] != -1) return dp[n][pr - 'a'];
        int res = 0;
        if(okA(pr)) {
            res += f(n - 1, 'a'); res %= mod;
        }

        if(okE(pr)) {
            res += f(n - 1, 'e'); res %= mod;
        }

        if(okI(pr)) {
            res += f(n - 1, 'i'); res %= mod;
        }

        if(okO(pr)) {
            res += f(n - 1, 'o'); res %= mod;
        }

        if(okU(pr)) {
            res += f(n - 1, 'u'); res %= mod;
        }

        return dp[n][pr - 'a'] = res;
    }

    int countVowelPermutation(int n) {
        int res = 0;
        dp.assign(n + 2, vector<int>(27, -1));
        
        for(char c : lst){
            res += f(n - 1, c); res %= mod;
        }

        return res;
    }
};
75021