解题思路
题意要求：一段长度为 n 的模式序列（字母表为 {1,…,9}），在“至多一次相邻交换”下得到的所有序列都必须没有相邻的两个 1（否则称为故障）。我们要统计这样的序列个数并对 109+7 取模。
关键等价化
把除 1 以外的数字都看作同一种“非 1”（记作 X），但每个 X 实际有 8 种取值。于是序列仅与“1 / 非1”的形态有关，最后再用 8非1个数 加权即可。
考虑一次相邻交换对是否出现“11”的影响。交换位置 i 与 i+1 的元素，仅可能新产生在三对相邻位置上的“11”：(i−1,i)、(i,i+1)、(i+1,i+2)。其中
