题目描述
称一个 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$。