// 二维动态规划的难题啊啊啊。
func numOfWays(n int) int {
// 所有满足条件的一行的可能性
// 0表示红，1表示蓝，2表示黄，使用十进制表示（210）10

types := make([][]int, 0)
numsOfColor := 3
// 所有满足条件的type
for i := 0; i < numsOfColor; i++ {
    for j := 0; j < numsOfColor; j++ {
        for k := 0; k < numsOfColor; k++ {
            if i != j && j != k {
                types = append(types, []int{i, j, k})
            }
        }
    }
}

// 下标代表types里头的type
typesColumn := make([][]int, len(types))
for i := 0; i < len(types); i++ {
    for j := 0; j < len(types); j++ {
        isok := true
        for k := 0; k < numsOfColor; k++ {
            if types[j][k] == types[i][k] {
                isok = false
            }
        }
        if isok {
            // 对每一种types返回其可以在下一行出现的types个数
            typesColumn[i] = append(typesColumn[i], j)
        }
    }
}
a := 1000000007
// i，j表示第i行，j为type时候的排列个数
dp := make([][]int, n)
for i := range dp {
    dp[i] = make([]int, len(types))
}

// 第一行
// 第二行
// dp[i][j] = dp[i - 1][k], k in coloumn[j]

// init 1
for i := 0; i < len(types); i++ {
    dp[0][i] = 1
}

for i := 1; i < n; i++ {
    for j := 0; j < len(types); j++ {
        for k := 0; k < len(typesColumn[j]); k++ {
            dp[i][j] += dp[i - 1][typesColumn[j][k]]
            dp[i][j] %= a
        }
    }
}
var res int
for i := 0; i < len(types); i++ {
    res += dp[n - 1][i]
    res %= a
}
return res

}