21266번 - Bit Operation 다국어

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$.

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$).

Print the answer.