题目描述

在准备学校文化节的过程中，强哥负责设计一个有趣的文字游戏。他得到了一个长度为 $n$ 的字符串 $s$，这个字符串由字母和问号组成。

强哥觉得这个字符串就像是拼图的关键，而那些问号则是需要同学们发挥创意来填补的部分。

他的任务是通过将问号巧妙地替换为小写字母，来构建一个完美的展示字符串。但有一个重要的规则：在替换完成后的整个字符串中，对于任何一个长度 $\ge 2$ 的连续子串，都不能出现某一个小写字母的数量超过这个连续子串长度的一半。

为了让更多同学参与进来，强哥想知道有多少种可能的替换方式能够满足这个条件。由于答案可能非常大，需要将结果对 $998244353$ 取模。

你能帮助强哥解决这个问题吗？

输入格式

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

输入第二行包含一个字符串 $s$，表示强哥获得的原始字符串。

输出格式

输出一行，表示满足条件的替换方式数量对 $998244353$ 取模的结果。

输入样例1

3
a?b

输出样例1

24

样例1解释

字符串中的问号可以替换为除 $a,b$ 以外任意的小写字母（共24个字母）。

输入样例2

3
a?a

输出样例2

0

数据规模与约定

• 对于 $30\%$ 的数据，保证 $n \le 8$。
• 对于 $50\%$ 的数据，保证 $n \le 200$。
• 对于另 $10\%$ 的数据，保证字符串中不存在问号。
• 对于 $100\%$ 的数据，保证 $1 \le n \le 5000$。