题目描述

当九分裤宝宝到达爆炸现场时，公民们已经吵了起来，有鼠甚至直接动起了手，整个一片鼠头攒动的景象。

但是九分裤宝宝注意到，在远处有一位公民，正不屑地、恶狠狠地盯着他，显然是看出了九分裤宝宝就是这件事情的始作俑者。

九分裤宝宝恼羞成怒，冲上去想要对他拳打脚踢，可这位公民直接打开地下的门钻了进去。

九分裤宝宝冲了上来，发现门上有这样一个游戏：

门上显示着一个长度为 $n$ 的、仅由 $0$ 和 $1$ 以及 $?$ 三种字符组成的字符串 $S$ ，和 $n + 1$ 个待填充的方框。设填充后第 $i$ 个方框内的字符串为 $T_i$ （从 $0$ 开始编号），它们需要满足以下要求：

• $T_0$ 为空串。 • $T_{i+1}$ 是在 $T_i$ 的基础上填入一个 $0$ 或 $1$ 得到的。 • $T_n$ 必须和 $S$ 模糊匹配，也即对于 $T_n$ 和 $S$ 中的每一组对应的字符，要么二者完全一致，要么存在 $?$ 字符。

九分裤宝宝心想：“这不白给吗。” 于是很快解出了这个游戏。结果，打开的门下又有另外一道门，要求在 $10$ 秒钟之内算出刚才的游戏的不同方案数对质数 $998244353$ 取模的结果，两种方案不同当且仅当存在 $i \in [0, n]$ ，满足两种方案中的 $T_i$ 不完全相同。

这下九分裤宝宝没辙了，随便蒙了一个答案，然而并没有正确，最后他被门上预留的炸弹给炸飞了。

门下的那位公民钻了出来，告诉了大家真相，大家为他惩治了坏蛋而欢呼，就在这时，一位小朋友突然指着他说：“这不是神话里智勇双全的 $qiuly$ 警长吗？”

大家惊奇地发现，这确实是 $CCF$ 行星盛传的神话里的 $qiuly$ 警长。就在大家想要上去要签名、合影的时候， $pcq$ 扔下的水到达了地表 ——

一代传奇就这样被毁灭了，和世人以及整个世界一起。

然而 $pcq$ 早就注意到了第二道门上的有趣的题目，他很想求出其答案。

输入格式

第一行输入一个整数 $n$ 。

第二行输入一个长度为 $n$ 的字符串 $S$ 。

输出格式

输出一行一个整数，表示答案。

数据范围

对于 $100\%$ 的数据，有 $1 \le n \le 5 \times 10^5$ 。

保证 $S$ 仅由 $0$ 、 $1$ 和 $?$ 三种字符组成。

子任务编号	$n \le$	特殊性质
$1$	$10$	无
$2$	$5 \times 10^5$	$A$
$3$		$B$
$4$	$5000$	无
$5$	$2 \times 10^5$
$6$	$5 \times 10^5$

特殊性质 $A$ ： $S$ 仅由 $?$ 字符组成。 特殊性质 $B$ ： $S$ 中 $0$ 和 $1$ 两种字符总共最多出现 $10$ 次。

输入样例 1

3
01?

输出样例 1

8

输入样例 2

9
0??001011

输出样例 2

32400

输入样例 3

40
1111111111111111111100000000000000000000

输出样例 3

88808106

样例解释

样例 $1$ 中，满足条件的方案有以下 $8$ 种：

$T_0$ 为空串， $T_1 = 0, T_2 = 00, T_3 = 010$ ； $T_0$ 为空串， $T_1 = 0, T_2 = 01, T_3 = 010$ ； $T_0$ 为空串， $T_1 = 0, T_2 = 01, T_3 = 011$ ； $T_0$ 为空串， $T_1 = 0, T_2 = 10, T_3 = 010$ ； $T_0$ 为空串， $T_1 = 1, T_2 = 01, T_3 = 010$ ； $T_0$ 为空串， $T_1 = 1, T_2 = 01, T_3 = 011$ ； $T_0$ 为空串， $T_1 = 1, T_2 = 10, T_3 = 010$ ； $T_0$ 为空串， $T_1 = 1, T_2 = 11, T_3 = 011$ 。