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

Example 1:

```Input: n = 1
Output: 5
Explanation: All possible strings are: "a", "e", "i" , "o" and "u".
```

Example 2:

```Input: n = 2
Output: 10
Explanation: All possible strings are: "ae", "ea", "ei", "ia", "ie", "io", "iu", "oi", "ou" and "ua".
```

Example 3:

```Input: n = 5
Output: 68```

Constraints:

• `1 <= n <= 2 * 10^4`

## Rust Solution

``````struct Solution;

const MOD: i64 = 1_000_000_007;

impl Solution {
fn count_vowel_permutation(n: i32) -> i32 {
let n = n as usize;
let mut a = vec![0; n];
let mut e = vec![0; n];
let mut i = vec![0; n];
let mut o = vec![0; n];
let mut u = vec![0; n];
a = 1;
e = 1;
i = 1;
o = 1;
u = 1;
for j in 1..n {
e[j] += a[j - 1];

a[j] += e[j - 1];
i[j] += e[j - 1];

a[j] += i[j - 1];
e[j] += i[j - 1];
o[j] += i[j - 1];
u[j] += i[j - 1];

i[j] += o[j - 1];
u[j] += o[j - 1];

a[j] += u[j - 1];

a[j] %= MOD;
e[j] %= MOD;
i[j] %= MOD;
o[j] %= MOD;
u[j] %= MOD;
}
((a[n - 1] + e[n - 1] + i[n - 1] + o[n - 1] + u[n - 1]) % MOD) as i32
}
}

#[test]
fn test() {
let n = 1;
let res = 5;
assert_eq!(Solution::count_vowel_permutation(n), res);
let n = 2;
let res = 10;
assert_eq!(Solution::count_vowel_permutation(n), res);
let n = 5;
let res = 68;
assert_eq!(Solution::count_vowel_permutation(n), res);
}
``````

Having problems with this solution? Click here to submit an issue on github.