You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

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

神的指示是一个字符串，记为字符串 s~1~，s~1~ 仅包含小写字母a-z。 现在小甲苯想要写下神的指示，记为字符串 s~2~，s~2~ 仅包含小写字母a-z，要求 s~1~ 中的相邻的两个字母不能在 s~2~ 中相邻地出现。

现在给定 s~2~ 的长度，小甲苯想知道他有多少种方法可以将神的指示写下来。 输出种类数对 10^9 + 7 取模的结果。 注意：题目中要求的不能相邻是指不能按原顺序相邻

Input

文件的第一行只有一个正整数 n，代表字符串 s~2~ 的长度，n <= 10^15。 第二行是一个字符串，代表字符串 s~1~。s~1~ 的长度不超过 100000。

Output

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

Samples

2
ab

675

Limitation

对于 30% 的数据，n ≤ 100000； 对于 100% 的数据，n ≤ 10^15。 1s, 1024KiB for each test case.