题目描述

称一个 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\le 8$。

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

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

提示