题目描述

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

输入格式

第一行只有一个正整数 $n$，代表字符串 $s_2$ 的长度。

第二行是一个字符串，代表字符串 $s_1$。

输出格式

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

2
ab

675

提示

• 对于 $30\%$ 的数据 $n\le100000$。
• 对于 $100\%$ 的数据 $1 \le n\le10^{15}$，$|s_1| \le 10^5$。

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