시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 1024 MB 5 5 5 100.000%

문제

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.

예제 입력 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