#4043. [TJOI2019] 甲苯先生的字符串

[TJOI2019] 甲苯先生的字符串

[TJOI2019] 甲苯先生的字符串

题目背景

TJOI2019 D1T1

源文件名:str.*

时间限制: 1s 内存限制: 128M

题目描述

一天小甲苯得到了一条神的指示,他要把神的指示写下来,但是又不能泄露天机,所以他要用一种方法把神的指示记下来。神的指示是一个字符串,记为字符串s1s_1s1s_1仅包含小写字母a − z。现在小甲苯想要写下神的指示,记为字符串s2s_2s2s_2仅包含小写字母a − z,要求s1s_1中的相邻的两个字母不能在s2s_2中相邻地出现。现在给定s2s_2的长度,小甲苯想知道他有多少种方法可以将神的指示写下来。输出种类数结果对109+710^9+7取模。

输入格式

第一行只有一个正整数nn,代表字符串s2s_2的长度,n1015n\le10^{15}

第二行是一个字符串,代表字符串s1s_1s1s_1的长度不超过100000100000

输出格式

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

样例 #1

样例输入 #1

2
ab

样例输出 #1

675

提示

对于30%的数据n100000n\le100000

对于100%的数据n1015n\le10^{15}

说明:相邻要求顺序相同,如样例中的s2s_2里不能出现abab,且仅不能出现abab,但可以出现baba.