비트 연산

길이가 $N$인 정수 배열 $A$가 주어진다. 배열의 원소는 $0$ 또는 $1$이다. 처음에 $a$는 배열 $A$와 같다. 다음 연산을 $N-1$번 수행한다.

• 현재 $a$의 길이를 $n$이라 하자. 정수 $i$ ($1 \leq i \leq n-1$)를 고르고, $a$의 $i$번째 원소와 $i+1$번째 원소를 삭제한다. 삭제한 두 원소를 각각 $x$, $y$라 하자. 삭제한 위치에 $x \mathbin{\&} y$ 또는 $x \mathbin{|} y$ 중 하나를 삽입한다. 여기서 $\&$는 비트 AND, $|$는 비트 OR이다.

연산을 수행하는 방법은 $2^{N-1} \times (N-1)!$가지이다. 최종적으로 값이 $1$인 원소 하나만 남는 방법의 수를 세어라. 답은 $998244353$으로 나눈 나머지를 구한다.

첫째 줄에 정수 $N$ ($1 \leq N \leq 10^6$)이 주어진다.

둘째 줄에 정수 $A_1, A_2, \ldots, A_N$ ($0 \leq A_i \leq 1$)이 주어진다.

답을 출력한다.