小清新计数题

小 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$。