[TJOI2019] 甲苯先生的字符串

题目背景

TJOI2019 D1T1 源文件名:str.* 时间限制: 1s 内存限制: 128M

题目描述

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

输入输出格式

输入格式


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

输出格式


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

输入输出样例

输入样例 #1

2
ab

输出样例 #1

675

说明

对于30%的数据$n\le100000$ 对于100%的数据$n\le10^{15}$ 说明:相邻要求顺序相同,如样例中的$s_2$里不能出现$ab$,且仅不能出现$ab$,但可以出现$ba$.