[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$取模

2
ab

675

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