TJOI2019D1T1·甲苯先生的字符串
- 时间限制：1s 内存限制：128M
题目描述
一天小甲苯得到了一条神的指示，他要把神的指示写下来，但是又不能泄露天机，所以他要用一种方法把神的指示记下来。神的指示是一个字符串，记为字符串\(s1\)，\(s1\)仅包含小写字母\(a − z\)。现在小甲苯想要写下神的指示，记为字符串\(s2\)，\(s2\)仅包含小写字母\(a − z\)，要求\(s1\)中的相邻的两个字母不能在\(s2\)中相邻地出现。现在给定\(s2\)的长度，小甲苯想知道他有多少种方法可以将神的指示写下来。输出种类数结果对\(10^9+7\)取模。
输入
第一行只有一个正整数\(n\)，代表字符串\(s2\)的长度，\(n\leq10^{15}\)。
第二行是一个字符串，代表字符串\(s1\)。\(s1\)的长度不超过\(100000\)。
输出
输出一个整数，表示小甲苯可以写出的字符串的总数。结果对\(10^9+7\)取模。
样例输入1
2
ab
样例输出1
675
数据范围
对于\(30\%\)的数据\(n\leq100000\)
对于\(100\%\)的数据\(n\leq10^{15}\)
题解
更多精彩
