QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 8639. 消除

Statistics

题目描述

称一个 01 序列是好的,当且仅当它可以实施如下操作最终变成空序列:

  • 每次操作你可以选择一个 0 并将它和它左边的第一个数删去,或者选择一个 1 并将它和它右边的第一个数删去。值得注意的是,你每次必须恰好删去两个数。例如你不能选择 011 中的 0,也不能选择 001 中的 1

以下给出了一些例子:

  • 好的序列例如 0100,因为你可以先选择 1 变成 00,在选择第二个 0 变为空序列。
  • 不好的序列例如 0101,不论选择第一个 1,还是选择第二个 0,序列都变成了 01

给定一个仅含有 01? 的序列,你要计算对于它的每一个子序列把每个 ? 变为 01,有多少种方案使最终的 01 序列是好的。你只需要输出你求出的所有答案的和,并对 $998244353$ 取模。

输入格式

从标准输入读入数据。

输入共两行。

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

第二行是一个长为 $n$ 且只包含 01? 的字符串。

输出格式

输出到标准输出。

输出一个整数,表示题目中所描述式子的答案。

样例

输入

4
1?1?

输出

16

样例

输入

10
1?0?1?????

输出

8078

解释

数据范围

对于 $10\%$ 的数据保证:$n\le 8$。

对于 $50\%$ 的数据保证:$n\le 5000$。

对于所有测试数据保证:$1\le n\le 10^6$。

提示