题目描述

你要登录某个神秘的系统，但你忘记了自己设置的密码。系统不支持重置密码，所以唯一的登录方式就是不断尝试。幸运的是，你还记得一些有关密码的信息：

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

然后你记住的信息可以用一个长度为 $n$ 的字符串 $S$ 来描述。假设 $S$ 的第 $i$ 个字符为 $s_i$，那么：

• 如果 $s_i$ 是大写字母或数字字符, 则密码的第 $i$ 个字符必须是 $s_i$;
• 如果 $s_i$ 是小写字母, 那么密码的第 $i$ 个字符可能是 $s_i$ 或 $s_i$ 的大写形式;
• 如果 $s_i$ 是问号 '?' , 那么密码的第 $i$ 个字符可以是任意大写字母、小写字母和数字字符。

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

此外, 系统对密码还有几点要求:

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

现在你想知道有多少种可能的密码。一个可能的密码应当既符合你的记忆, 又符合系统的要求, 并且数据保证至少存在一个可能的密码。

答案对 $998244353$ 取模。请注意不常见的内存限制。

输入格式

从 password.in 文件读入数据。

第一行一个整数 $n$ 。

第二行一个字符串 $S$，保证字符串 $S$ 仅包含大写字母、小写字母、数字字符和问号 '?' 。

输出格式

输出到 password.out 文件。

输出一行一个整数，代表答案模 $998244353$ 。保证至少存在一种可能的密码。

样例

4
a?0B

86

样例 2

点击链接 ex_password2.in 和 ex_password2.out 下载大样例 2 的输入数据和输出数据。

数据范围

对于所有数据，$1 \leq n\leq 10^5$，保证字符串 $S$ 仅包含大写字母、小写字母、数字字符和问号 '?' 。