题目描述

小 A 正在电脑上玩一个叫做 Truth or Lie 的游戏。

游戏开始时电脑会给出 $n$ 句话，每句话形如“第 $x$ 句话为真”或“第 $x$ 句话为假”，其中 $x$ 是一个 $1$ 到 $n$ 的整数，你只要选择“Good”或者“Bad”，“Good”表示可以决定每句话的真假使每句话的内容都成立，“Bad”反之。

作为一个菜鸡，小 A 只会不停地点“Good”，靠脸过关。

在无数次失败后，非洲人小 A 发现游戏每关中，每句话包含的是“真”还是“假”是固定的，但是每句话中的 $x$ 是在 $1$ 到 $n$ 均匀随机的。

现在小 A 告诉了你某一关每句话的真假，用一个 $01$ 序列表示。第 $i$ 位为 $0$ 表示第 $i$ 句话包含“假”，否则表示包含“真”。现在他想要知道使得点击“Good”正确的方案数。

由于方案数可能比较大，你需要输出方案数对 $998244353$ 取模的结果。

（读不懂题的请移步样例解释）

输入格式

一行一个 $01$ 序列，它的长度即为 $n$。

输出格式

输出方案数对 $998244353$ 取模的结果。

01

1

10101

1154

10101101010111110100110100101010110001010010101001

322173207

提示

样例解释

第一句话的内容为“某句话为假”，第二句话的内容为“某句话为真”。所有可能情况如下：

1. 第一句话的内容为“第一句话为假”，第二句话的内容为“第一句话为真”，结果应为 Bad。

2. 第一句话的内容为“第一句话为假”，第二句话的内容为“第二句话为真”，结果应为 Bad。

3. 第一句话的内容为“第二句话为假”，第二句话的内容为“第一句话为真”，结果应为 Bad。

4. 第一句话的内容为“第二句话为假”，第二句话的内容为“第二句话为真”，结果应为 Good，因为只需认为第一句话为假，第二句话为真就符合两句话，所以是 Good。

所以共有一种合法方案。

数据范围

• 对于$10\%$ 的数据，$n \leq 7$；
• 对于$20\%$ 的数据，$n \leq 9$；
• 对于$60\%$ 的数据，$n \leq 20$；
• 对于$100\%$ 的数据，$1 \leq n \leq 50$。