解题思路

题意要求：一段长度为 $n$ 的模式序列（字母表为 $\{1,\dots,9\}$），在“至多一次相邻交换”下得到的所有序列都必须没有相邻的两个 1（否则称为故障）。我们要统计这样的序列个数并对 $10^9+7$ 取模。

关键等价化 把除 1 以外的数字都看作同一种“非 1”（记作 $X$），但每个 $X$ 实际有 8 种取值。于是序列仅与“1 / 非1”的形态有关，最后再用 $8^{\text{非1个数}}$ 加权即可。

考虑一次相邻交换对是否出现“11”的影响。交换位置 $i$ 与 $i+1$ 的元素，仅可能新产生在三对相邻位置上的“11”：$(i-1,i)$、$(i,i+1)$、$(i+1,i+2)$。其中

题目内容

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

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

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

输入描述

输入一行，包含一个整数 $n$ ，其中 $1≤n≤100000$，表示信号灯序列的长度。

输出描述

输出一行，包含一个整数，表示长度为 $n$ 的可靠信号灯序列的种类数。答案对 $1000000007$ 取模。

样例1

输入

2

输出

80

说明

长度为 $2$ 的信号灯序列共有 $9^2-81$ 种，其中 $11$ 为不可靠信号灯序列，$81-1=80$ 。

样例2

输入

3

输出

704