你需要登录一个神秘系统，但你发现自己忘记了密码。该系统不支持重置密码，因此登录的唯一方法是不断尝试。

幸运的是，你还记得关于密码的一些信息：

首先，你确定密码的长度为 $n$。

然后，你记得的信息可以用一个长度为 $n$ 的字符串 $s$ 来描述。 令 $s_i$ 表示 $s$ 的第 $i$ 个字符：

• 如果 $s_i$ 是大写字母或数字，则密码的第 $i$ 个字符必须是 $s_i$；
• 如果 $s_i$ 是小写字母，则密码的第 $i$ 个字符可能是 $s_i$ 或 $s_i$ 的大写形式；
• 如果 $s_i$ 是问号 ‘?’，则密码的第 $i$ 个字符可以是任何大写字母、小写字母或数字。

保证字符串 $s$ 仅包含大写字母、小写字母、数字和问号 ‘?’。

此外，系统对密码还有几项要求：

• 密码中至少出现一个大写字母；
• 密码中至少出现一个小写字母；
• 密码中至少出现一个数字；
• 密码中任意两个相邻字符不能相同。

现在你想知道，有多少种可能的密码？一个可能的密码应该同时符合你的记忆和系统的要求，且保证至少存在一个可能的密码。

你知道这个答案会非常大，所以你只需要计算结果对 998244353 取模后的值。

请注意该题不同寻常的内存限制。

输入格式

第一行包含一个整数 $n$ ($3 \le n \le 10^5$)，表示密码的长度。 第二行包含一个长度为 $n$ 的字符串 $s$。保证字符串 $s$ 仅包含大写字母、小写字母、数字和问号 ‘?’。 保证至少存在一个可能的密码。

输出格式

输出一行，包含一个整数，表示答案对 998244353 取模后的结果。

样例

输入 1

4
a?0B

输出 1

86