Yana、Mino、White 和 Huzz 是最好的朋友。

Mino 最近感到很迷茫。由于沉迷于过去在 OI 中的失败，他在管理繁忙的学校日程的同时，一直难以规划自己的未来。他的三个朋友建议他评估各项任务的重要性并确定优先级。

假设有 $n$ 个不同的任务，编号为 $1$ 到 $n$。每次，Huzz 选择两个相邻的任务，White 对它们进行比较，Yana 将它们合并为一个任务。Mino 惊讶地发现，这个过程意外地形成了一棵线段树，这棵树不一定从中间分裂。更具体地说，它形成了一棵拥有 $2n - 1$ 个节点的树，其中每个子树都对应一个连续的区间。注意，所有 $n$ 个任务都是叶子节点，而其他 $n - 1$ 个节点每个都有两个子节点。这些由比较产生的节点定义了指向其子节点的边权：指向较小子节点的边权为 $0$，指向较大子节点的边权为 $1$。

Mino 非常喜欢计算。他将每个任务的权值定义为从该任务到根节点的路径上所有边权的异或和。他想知道：如果给定这些权值，有多少种方法可以构建这样的树并进行子节点的比较？

同样，Mino 并不擅长 OI，这就是他向你寻求帮助的原因。为了简化问题，你只需要求出答案模 $998,244,353$ 的结果。

输入格式

第一行包含一个正整数 $n$ ($1 \le n \le 250000$)，表示任务的数量。

第二行包含一个长度为 $n$ 的二进制字符串 $S$，其中 $S_i$ 表示从任务 $i$ 到根节点的路径上所有边权的按位异或和。

输出格式

输出一个整数，即答案模 $998,244,353$ 的结果。

样例

输入样例 1

4
0101

输出样例 1

6

说明

有 6 种构建树并比较子节点的方法：