1s 512MB

题目描述

沙皇热爱兵乓球，具体的，沙皇会喊来一个神金兵，并给他一个空序列，然后神金兵要进行 $n$ 次操作，每次在这个序列任意位置插入一个球，可以是黑色也可以是白色，沙皇想知道本质不同的操作方案数，具体的，设第 $i$ 次操作后的序列为 $s_i$， $s_0$ 为空，就是要数 $\{s_1,s_2,\cdots,s_n\}$ 不同的集合个数

这当然难不倒训练有素的神金兵，沙皇决定顺便考察一下神金兵的忠诚程度，沙皇的任何指示都要去做，哪怕是比登天还难！所以沙皇限定了 $s_n$，也就是限定了结束序列每个位置的球的颜色，不过有些位置可能沙皇懒得管，可以任意放黑白球，现在再来求求方案数吧！神金兵大统领！

由于答案是一个很大很大的数，沙皇不想让你花过多的时间在这里，同时他已经用 $10^{-\mathrm E} s$ 算出了结果，所以你只需要告诉沙皇答案对 $998244353$ 取模的结果让他验证一下即可。

输入格式

第一行一个数 $n$ ，意思见题目描述，第二行一个字符串 $s_n$，第 $i$ 位为 $0$ 代表这一位必须是白球，$1$ 则是黑球，$?$ 则表示沙皇懒得管，随便。

输出格式

一行一个数，表示本质不同的操作方案数对 $998244353$ 取模的结果。

样例一输入

3
01?

样例一输出

8

样例一解释

$8$ 种本质不同的操作方案如下

$\{0,00,010\},\{0,01,010\},\{0,01,011\},\{0,10,010\},\{1,01,010\},\{1,01,011\},\{1,10,010\},\{1,11,011\}$

样例二输入

9
0??001011

样例二输出

32400

数据范围与约束

对于 $100 \%$ 的数据， $1 \le n \le 5000$

$\text{subtask1 (3pts)}$ ： $n=1$

$\text{subtask2 (7pts)}$ ： $n \le 8$

$\text{subtask3 (15pts)}$ ： $n \le 18$

$\text{subtask4 (15pts)}$ ： $n \le 50$

$\text{subtask5 (15pts)}$ ： $n \le 300$

$\text{subtask6 (5pts)}$ ： $\forall i \in [1,n],s_i= \texttt{?}$

$\text{subtask7 (10pts)}$ ： $\forall i \in [1,n],s_i\not= \texttt{?}$

$\text{subtask8 (30pts)}$ ： $n \le 5000$

文明的出题人不开子任务依赖！快来赞美良心的出题人吧！