题目内容

某交通枢纽采用智能信号灯系统，该系统支持九种模式，用编号 $1$ ~ $9$ 来表示。信号灯会按时间顺序输出一段长度为 $n$ 的模式序列(例如:$137632...$)。

系统有严格的安全约束:若序列中存在两个相邻的 $1$ 号模式，会触发设备故障，称为“故障序列”;反之，无相邻 $1$ 号模式的序列称为“正常序列”。例如:$124、2418、1$ 是正常序列;$11、8111、61192$ 是故障序列。

由于硬件特性，信号灯在切换模式时至多会出现一次“相邻模式交换”的误差(例如序列 $123$ 可能变成 $132$ )。若一段序列在“至多交换一次相邻模式”的条件下，得到的所有结果均为正常序列，则称其为“可靠信号灯序列”;若交换后可能得到故障序列，则称其为“不可靠信号灯序列”。例如:$124、1、123123$ 是可靠信号灯序列;$24141、1214、311$ 是不可靠信号灯序列。请计算有多少种不同的长度为n的可靠信号灯序列，结果对 $1000000007$ 取模。