408064: GYM102978 B 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.

3
0 1 0

2

5
1 1 1 1 1

384

7
0 1 1 0 1 0 1

25515