题目描述

小可拿到了一个长度为 $n$ 且只包含 0、1、? 的字符串 $s$ 小可认为一个二进制串是平衡的，当且仅当相邻两个字符相同的对数是偶数。

特别的，长度为 $1$ 的01串也是平衡的，因为此时对数为 $0$。

现在小可要将所有的 ? 替换为 0 或者 1 ，你的任务是求出在所有可能的替换字符串中，有多少个 01 二进制串是平衡的?结果对$998244353$ 取模。

输入格式

一行一个字符串 s。

输出格式

输出满足条件的二进制串数量。

样例

0?1

0

????

8

样例解释

第一组数据：$s = 0?1$，两种替换：

"$001$"：相邻相同对数为 $1$（"$00$"），奇数，不平衡。

"$011$"：相邻相同对数为 $1$（"$11$"），奇数，不平衡。

输出 $0$。

数据范围

前 $30$ 分，保证 $1 \le |s| \le 10^3$，且问号的数量 $\le 10$。

$100$ 分，$1 \leq |s| \leq 5 \times 10^5$。