题目描述

给定一个长度为 $n$、仅包含字符 0、1 和 ? 的字符串 $S$。

需要计算满足下列条件的字符串序列

的数量：

1. $T_i$ 的长度恰好为 $i$，并且只包含字符 0 和 1；
2. 对于每个 $i\in[1,n]$，字符串 $T_i$ 可以由 $T_{i-1}$ 插入一个字符 0 或 1 得到；
3. 对于最终字符串 $T_n$ 的每一位 $i$：
   • 若 $S_i$ 为 0 或 1，则必须满足 $T_{n,i}=S_i$；
   • 若 $S_i$ 为 ?，则 $T_{n,i}$ 可以为 0 或 1。

求方案数对

取模后的结果。

其中，$T_0$ 是空字符串。

输入格式

第一行包含一个整数 $n$。

第二行包含一个长度为 $n$、仅由 0、1 和 ? 构成的字符串 $S$。

输出格式

输出一行一个整数，表示满足条件的方案数量对 $998244353$ 取模后的结果。

样例 1

输入

3
0?1

输出

6

样例解释

满足条件的 $6$ 种方案分别为：

1. $T_1=0,\ T_2=00,\ T_3=001$；
2. $T_1=0,\ T_2=01,\ T_3=001$；
3. $T_1=1,\ T_2=01,\ T_3=001$；
4. $T_1=1,\ T_2=11,\ T_3=011$；
5. $T_1=0,\ T_2=01,\ T_3=011$；
6. $T_1=1,\ T_2=01,\ T_3=011$。

样例 2

输入

5
0111?

输出

24

数据范围与子任务

对于全部测试数据：

特殊性质 A

字符串 $S$ 仅包含字符 ?。

特殊性质 B

字符串 $S$ 中字符 0 和 1 的出现次数之和不超过 $10$。