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.

제한

힌트