> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/dynamic/graph.md).

# Graph

## 1220. Count Vowels Permutation

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.`

![](https://2249014260-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LrHBOmnlXe2UPlScnAC%2F-MJQYsICKSo6btjFxOTJ%2F-MJQaCeghXUi22myMzP_%2FScreen%20Shot%202020-10-12%20at%202.56.24%20PM.png?alt=media\&token=ea650f7c-a3c5-4128-8187-06e3c35ee3c9)

```python
def countVowelPermutation(self, n: int) -> int:
    MOD = 10**9 + 7
    dp = [[0] * 5 for _ in range(n)] # ['a', 'e', 'i', 'o', 'u']
    for j in range(5):
        dp[0][j] = 1
    
    for i in range(1, n):
        dp[i][0] = (dp[i-1][1] + dp[i-1][2] + dp[i-1][4]) % MOD
        dp[i][1] = (dp[i-1][0] + dp[i-1][2]) % MOD
        dp[i][2] = (dp[i-1][1] + dp[i-1][3]) % MOD
        dp[i][3] = (dp[i-1][2]) % MOD
        dp[i][4] = (dp[i-1][2] + dp[i-1][3]) % MOD
        
    res = 0
    for j in range(5):
        res = (res + dp[n-1][j]) % MOD
    return res
```

1-D array

```python
def countVowelPermutation(self, n: int) -> int:
    a, e, i, o, u = 1, 1, 1, 1, 1
    
    for _ in range(n - 1):
        a,e,i,o,u = e + i + u, a + i, e + o, i, i + o
    return (a + e + i + o + u) % (10**9 + 7)
```