B. Bit Operation
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given an integer array $$$A$$$ of length $$$N$$$, consisting of $$$0$$$'s and $$$1$$$'s. Let $$$a$$$ be initially the array $$$A$$$. You are going to perform the following operation $$$N-1$$$ times.

  • Let $$$n$$$ be the current length of $$$a$$$. Choose an integer $$$i$$$ ($$$1 \leq i \leq n-1$$$) and delete the $$$i$$$-th and the $$$(i+1)$$$-th elements of $$$a$$$. Then, by letting $$$x$$$ and $$$y$$$ be the deleted elements, insert either $$$x\mathbin{\&}y$$$ or $$$x\mathbin{|}y$$$ to the position of the deleted elements. Here $$$x\mathbin{\&}y$$$ and $$$x\mathbin{|}y$$$ denote the bit-AND and bit-OR operations, respectively.

There are $$$2^{N-1} \times (N-1)!$$$ ways to perform the operations. Count the number of ways that result in a single value of $$$1$$$, modulo $$$998244353$$$.

Input

The first line contains an integer $$$N$$$ ($$$1 \leq N \leq 10^6$$$).

The second line contains integers $$$A_1,A_2,\ldots,A_N$$$ ($$$0 \leq A_i \leq 1$$$).

Output

Print the answer.

Examples
Input
3
0 1 0
Output
2
Input
5
1 1 1 1 1
Output
384
Input
7
0 1 1 0 1 0 1
Output
25515