给定一个长度为 $N$ 的整数数组 $A$，其中包含 $0$ 和 $1$。令 $a$ 初始为数组 $A$。 你将执行以下操作 $N - 1$ 次：

• 设 $n$ 为 $a$ 的当前长度。选择一个整数 $i$ ($1 \le i \le n - 1$)，并删除 $a$ 中的第 $i$ 个和第 $(i + 1)$ 个元素。然后，设 $x$ 和 $y$ 为被删除的元素，在被删除元素的位置插入 $x \ \& \ y$ 或 $x \ | \ y$。这里 $x \ \& \ y$ 和 $x \ | \ y$ 分别表示按位与（bit-AND）和按位或（bit-OR）运算。

执行这些操作共有 $2^{N-1} \times (N - 1)!$ 种方式。请计算最终结果为 $1$ 的方式数量，对 $998244353$ 取模。

输入格式

第一行包含一个整数 $N$ ($1 \le N \le 10^6$)。 第二行包含整数 $A_1, A_2, \dots, A_N$ ($0 \le A_i \le 1$)。

输出格式

输出答案。

样例

输入 1

3
0 1 0

输出 1

2

输入 2

5
1 1 1 1 1

输出 2

384

输入 3

7
0 1 1 0 1 0 1

输出 3

25515