#3104. 「TJOI2019」甲苯先生的字符串

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: LoveAmy

题目描述

一天小甲苯得到了一条神的指示,他要把神的指示写下来,但是又不能泄露天机,所以他要用一种方法把神的指示记下来。

神的指示是一个字符串,记为字符串 s_1 s_1 仅包含小写字母 \texttt{a-z}
现在小甲苯想要写下神的指示,记为字符串 s_2 s_2 仅包含小写字母 \texttt{a-z} ,要求 s_1 中的相邻的两个字母不能在 s_2 中相邻地出现。

现在给定 s_2 的长度,小甲苯想知道他有多少种方法可以将神的指示写下来。
输出种类数对 10^9 + 7 取模的结果。

输入格式

文件的第一行只有一个正整数 n ,代表字符串 s_2 的长度, n \le 10^{15}
第二行是一个字符串,代表字符串 s_1 s_1 的长度不超过 100000

输出格式

输出一个整数,表示小甲苯可以写出的字符串的总数。
结果对 10^9 + 7 取模。

样例

样例输入

2
ab

样例输出

675

数据范围与提示

对于 30\% 的数据, n ≤ 100000
对于 100\% 的数据, n ≤ 10^{15}