package main import ( "fmt" "math" ) func main() { var n int _, _ = fmt.Scan(&n) mod := int(math.Pow10(9)) + 7 k := []int{0, 1, 0} // 0: ケンが0回連続している状態, 1: ケンが1回連続している状態, 2: ケンが2回連続している状態 // 状態の遷移 // [1, 0, 0] -> [0, 1, 0] // パの状態からはケンしかできない // [0, 1, 0] -> [1, 0, 1] // ケンの状態からはパかケンを選択できる // [0, 0, 1] -> [1, 0, 0] // ケンケンの状態からはパしかできない for i := 1; i < n; i++ { t := make([]int, 3) t[0] = (k[1] + k[2]) % mod t[1] += k[0] t[2] += k[1] // fmt.Println(i, k, t) k = t } fmt.Println((k[0] + k[1] + k[2]) % mod) }