该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师来到了一个神秘的石洞，但是这个石洞被一扇充满科技感的门封死了

石老师告诉徐老师，也许石洞里有外星人留下的羊腿！（外星人为什么会留下羊腿？？）

众所周知，没有人能够抵抗羊腿的诱惑，特别是徐老师

于是徐老师准备研究研究如何打开石洞，他发现石洞的门上写着长度为 $n$ 的字符串 $S$

这个字符串每隔一段时间就会发生变化，经过徐老师的观察，他发现这个字符串里只会出现小写字母和问号

而经过他不断的探索，他发现字符串上的问号是可以被点击的，当点击后，徐老师可以将这个问号替换成任意一个小写字母，而当所有问号被替换成字母后，这扇门会明显进入判定状态，显然是在查看这个字符串能否开门

经过徐老师不断的测试，最终徐老师打开了这扇神秘的大门！

而经过徐老师的总结，开门的规则是——最终的字符串 $S$ 中，不能有任意长度 $\ge 2$ 的连续子串中存在出现次数 超过 这个子串长度一半的小写字母

好不容易打开了门的徐老师发现门背后其实什么都没有，这真是个悲伤的故事！

痛定思痛的徐老师决定静下心来好好思考，对于一个字符串，到底有多少种不同的开门方式？

输入格式

输入第一行包含一个整数 $n$，表示字符串的长度

输入第二行包含一个字符串 $S$，表示徐老师现在看到门上的字符串

输出格式

输出包含一个整数，表示有多少种不同的字符串可以打开这门，由于答案很大，请将答案对 $10^9+7$ 取模后输出

如果没有能开门的方案，则输出 Sorry!

数据范围

对于所有输入数据保证：输入的字符串仅包含小写字母和英文问号

样例输入1

3
x?y

样例输出1

24

样例解释1

如果替换成 $x$，字符串变成 $xxy$，可以发现子串 $xx$ 不满足条件 如果替换成 $y$，字符串变成 $xyy$，可以发现子串 $yy$ 不满足条件 其余字母均符合条件

样例输入2

3
a?a

样例输出2

Sorry!

样例输入3

6
x?y?za

样例输出3

530