样例文件

题目描述

Alice 用小写英文字母构造了一个字符串，记为 A。

Bob 也想构造一个字符串，记为 B。要求：

• B 的长度为 n。
• B 中字符全部为小写英文字母。
• 对于 A 中的任意一个长度大于 1 的子串，都不允许在 B 中出现。（所谓子串，是指由原字符串中的若干个连续字符按原顺序组成的字符串。）

问：Bob 最多能构造出多少个不同的字符串 B？

答案可能很大，你需要将其 $mod (10^9+7)$ 后输出。

输入格式

第一行：$n$

第二行：字符串 A。

输出格式

一个整数，表示答案 $mod (10^9+7)$

样例输入

2
abc

样例输出

674

提示

30%的数据，$n ≤ 10^5$

100%的数据，$n ≤ 10^{15}$，$|A| ≤ 10^5$，$A$中字符全部为小写英文字母。