408064: GYM102978 B Bit Operation
Memory Limit:1024 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
B. Bit Operationtime limit per test2 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output
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$$$.
InputThe 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$$$).
OutputPrint the answer.
ExamplesInput3 0 1 0Output
2Input
5 1 1 1 1 1Output
384Input
7 0 1 1 0 1 0 1Output
25515