#P16386. [2024年南京集训]消逝的传承

[2024年南京集训]消逝的传承

题目描述

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

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

(T0,T1,T2,…,Tn)(T_0,T_1,T_2,\ldots,T_n)

的数量:

  1. TiT_i 的长度恰好为 ii,并且只包含字符 0 和 1;
  2. 对于每个 i∈[1,n]i\in[1,n],字符串 TiT_i 可以由 Ti−1T_{i-1} 插入一个字符 0 或 1 得到;
  3. 对于最终字符串 TnT_n 的每一位 ii:
    • 若 SiS_i 为 0 或 1,则必须满足 Tn,i=SiT_{n,i}=S_i;
    • 若 SiS_i 为 ?,则 Tn,iT_{n,i} 可以为 0 或 1。

求方案数对

998244353998244353

取模后的结果。

其中,T0T_0 是空字符串。

输入格式

第一行包含一个整数 nn。

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

输出格式

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

样例 1

输入

3
0?1

输出

6

样例解释

满足条件的 66 种方案分别为:

  1. T1=0, T2=00, T3=001T_1=0,\ T_2=00,\ T_3=001;
  2. T1=0, T2=01, T3=001T_1=0,\ T_2=01,\ T_3=001;
  3. T1=1, T2=01, T3=001T_1=1,\ T_2=01,\ T_3=001;
  4. T1=1, T2=11, T3=011T_1=1,\ T_2=11,\ T_3=011;
  5. T1=0, T2=01, T3=011T_1=0,\ T_2=01,\ T_3=011;
  6. T1=1, T2=01, T3=011T_1=1,\ T_2=01,\ T_3=011。

样例 2

输入

5
0111?

输出

24

数据范围与子任务

对于全部测试数据:

1≤n≤5×105.1\le n\le 5\times 10^5.
子任务 nn 不超过 特殊性质 分值
1 55 无 10
2 1515
3 5×1055\times 10^5 A 5
4 B 25
5 5×1025\times 10^2 无 10
6 5×1035\times 10^3
7 2×1052\times 10^5 15
8 5×1055\times 10^5

特殊性质 A

字符串 SS 仅包含字符 ?。

特殊性质 B

字符串 SS 中字符 0 和 1 的出现次数之和不超过 1010。