给你一个整数 n，请你帮忙统计一下我们可以按下述规则形成多少个长度为 n 的字符串：

    字符串中的每个字符都应当是小写元音字母（’a’, ‘e’, ‘i’, ‘o’, ‘u’）
    每个元音 ‘a’ 后面都只能跟着 ‘e’
    每个元音 ‘e’ 后面只能跟着 ‘a’ 或者是 ‘i’
    每个元音 ‘i’ 后面 不能 再跟着另一个 ‘i’
    每个元音 ‘o’ 后面只能跟着 ‘i’ 或者是 ‘u’
    每个元音 ‘u’ 后面只能跟着 ‘a’
    由于答案可能会很大，所以请你返回 模 10^9 + 7 之后的结果。

    示例 1：

    输入：n = 1
    输出：5
    解释：所有可能的字符串分别是：”a”, “e”, “i” , “o” 和 “u”。
    示例 2：

    输入：n = 2
    输出：10
    解释：所有可能的字符串分别是：”ae”, “ea”, “ei”, “ia”, “ie”, “io”, “iu”, “oi”, “ou” 和 “ua”。
    示例 3：

    输入：n = 5
    输出：68

    提示：

    1 <= n <= 2 * 10^4

    dp

    1. class Solution {
    2.     static int mod = (int)1e9 + 7;
    3.     public int countVowelPermutation(int n) {
    4.         //f[i][j]表示长度为i+1，且以j结尾的字符串方案数集合
    5.         long[][] f = new long[n+10][5];
    6.         //初始化
    7.         for (int i = 0; i < 5; ++i) f[0][i] = 1;
    8.         for (int i = 1; i < n; ++i) {
    9.             //'a'后面只能跟着'e'
    10.             f[i][1] += f[i-1][0];
    11.             //'e'后面只能跟着'a'或'i'
    12.             f[i][0] += f[i-1][1];
    13.             f[i][2] += f[i-1][1];
    14.             //'i'后面不能跟'i'
    15.             for (int j = 0; j < 5; ++j) 
    16.                 if (j != 2) f[i][j] += f[i-1][2];
    17.             //'o'后面只能跟着'i'或'u'
    18.             f[i][2] += f[i-1][3];
    19.             f[i][4] += f[i-1][3];
    20.             //'u'后面只能跟着'a'
    21.             f[i][0] += f[i-1][4];
    22.             //取模
    23.             for (int j = 0; j < 5; ++j) f[i][j] %= mod;
    24.         }
    25.         long res = 0;
    26.         for (int i = 0; i < 5; ++i) res += f[n-1][i];
    27.         return (int)(res % mod);
    28.     }
    29. }

    矩阵快速幂