题目描述
称一个 01
序列是好的,当且仅当它可以实施如下操作最终变成空序列:
- 每次操作你可以选择一个
0
并将它和它左边的第一个数删去,或者选择一个1
并将它和它右边的第一个数删去。值得注意的是,你每次必须恰好删去两个数。例如你不能选择011
中的0
,也不能选择001
中的1
。
以下给出了一些例子:
- 好的序列例如
0100
,因为你可以先选择1
变成00
,在选择第二个0
变为空序列。 - 不好的序列例如
0101
,不论选择第一个1
,还是选择第二个0
,序列都变成了01
。
给定一个仅含有 0
,1
,?
的序列,你要计算对于它的每一个子序列把每个 ?
变为 0
或 1
,有多少种方案使最终的 01
序列是好的。你只需要输出你求出的所有答案的和,并对 998244353 取模。
输入格式
从标准输入读入数据。
输入共两行。
第一行包含一个正整数 n。
第二行是一个长为 n 且只包含 0
,1
,?
的字符串。
输出格式
输出到标准输出。
输出一个整数,表示题目中所描述式子的答案。
样例
输入
4
1?1?
输出
16
样例
输入
10
1?0?1?????
输出
8078
解释
数据范围
对于 10% 的数据保证:n≤8。
对于 50% 的数据保证:n≤5000。
对于所有测试数据保证:1≤n≤106。