P5337 [TJOI2019] 甲苯先生的字符串
题目背景
TJOI2019 D1T1
源文件名:str.*
时间限制: 1s 内存限制: 128M
题目描述
一天小甲苯得到了一条神的指示,他要把神的指示写下来,但是又不能泄露天机,所以他要用一种方法把神的指示记下来。神的指示是一个字符串,记为字符串 $s_1$,$s_1$ 仅包含 $26$ 个小写字母。现在小甲苯想要写下神的指示,记为字符串 $s_2$,$s_2$ 仅包含 $26$ 个小写字母,要求 $s_1$ 中的相邻的两个字母不能在 $s_2$ 中相邻地出现。现在给定 $s_2$ 的长度,小甲苯想知道他有多少种方法可以将神的指示写下来。输出种类数结果对 $10^9+7$ 取模。
输入格式
无
输出格式
无
说明/提示
对于 $30\%$ 的数据 $n\le100000$。
对于 $100\%$ 的数据 $1 \le n\le10^{15}$,$|s_1| \le 10^5$。
说明:相邻要求顺序相同,如样例中的 $s_2$ 里不能出现 $\text{ab}$,且仅不能出现 $\text{ab}$,但可以出现 $\text{ba}$。