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.

题目描述

在探索神秘的字符世界的过程中，小 E 遇到了一个有趣的挑战。

他得到了一个长度为 $n$ 的字符串 $s$，这个字符串由一些神秘的问号和小写字母组成。

小 E 觉得这个字符串就像是一把能解开字符世界秘密的钥匙，而那些问号则是等待他去揭开的关键未知元素。

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

为了找到所有满足这种苛刻条件的可能性，小 E 希望能知道有多少种可能的替换方式。但由于最终的答案可能非常巨大，需要将答案对 $998244353$ 取余，以便得到一个合理且便于处理的结果。

你能帮帮他吗？

输入格式

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

输入第二行包含一个字符串 $s$，表示小 E 获得的字符串。

输出格式

输出共一行，表示最少需要使用多少次武器。若不能击败，则输出 $-1$。

样例 1 输入

3
a?b

样例 1 输出

24

样例 1 解释

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

样例 2 输入

3
a?a

样例 2 输出

0

其余样例见下发文件。

数据规模与约定

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