# Leetcode 1220 - Count Vowels Permutation

`Note:`

- Since from the end char of prev permutation, we can get next permutation. It looks like a
`DP`

problem! - Let
`dp[i][j]`

be the number of permutations of a string with length`i`

and ending with`vowel[j]`

. - From the rules, we can deduct that
`a`

follows`e, i, u`

.`e`

follows`a, i`

.`i`

follows`e, o`

.`o`

follows`i`

.`u`

follows`o, i`

.

- For example, if the vowel is
`a`

, then it must appear after`e, i, u`

, so we can just add the number of permutations that end with`e, i, u`

. Then what we get would be the number of permutations ending with`a`

.

`Question:`

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

- Each character is a lower case vowel (‘a’, ‘e’, ‘i’, ‘o’, ‘u’)
- Each vowel ‘a’ may only be followed by an ‘e’.
- Each vowel ‘e’ may only be followed by an ‘a’ or an ‘i’.
- Each vowel ‘i’ may not be followed by another ‘i’.
- Each vowel ‘o’ may only be followed by an ‘i’ or a ‘u’.
- Each vowel ‘u’ may only be followed by an ‘a’.

Since the answer may be too large, return it modulo 10^9 + 7.

`Example:`

1 | Input: n = 2 |

`Code:`

1 | /** |