[AdditionalFile3104.zip](file://AdditionalFile3104.zip?type=additional_file)

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

标签: 传统 | 时间限制: 1000 ms | 内存限制: 128 MiB |

题目描述

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

神的指示是一个字符串，记为字符串 $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

说明

说明：相邻要求顺序相同，如样例中的 $s_2$ 里不能出现 ab，且仅不能出现 ab，但可以出现 ba。

数据范围与提示

对于 $30\%$ 的数据，$n ≤ 100000$；
对于 $100\%$ 的数据，$n ≤ 10^{15}$。