Monotone Sequences with XOR Zero

Given a non-decreasing sequence \(a\) of \(n\) integers, i.e. \(a_1 \le a_2 \le \cdots \le a_n\), you need to count the number of sequences \(b\) of length \(2n-1\) satisfying the following conditions:

• For every \(1\le i\le n\), \(b_{2i-1} = a_i\).
• The sequence \(b\) is non-decreasing.
• The bitwise XOR of all elements of \(b\) is zero. In other words, \(b_1 \oplus b_2 \oplus \cdots \oplus b_{2n-1} = 0\), where \(\oplus\) denotes the bitwise XOR operation.

Since the odd positions of \(b\) are fixed by \(a\), the even positions \(b_2, b_4, \ldots, b_{2n-2}\) can be chosen arbitrarily provided they satisfy the monotonicity condition. Specifically, for every \(1 \le i \le n-1\), we must choose an integer \(x_i = b_{2i}\) such that

[ a_i \le x_i \le a_{i+1}. ]

The XOR condition now becomes:

[ a_1 \oplus a_2 \oplus \cdots \oplus a_n \oplus (x_1 \oplus x_2 \oplus \cdots \oplus x_{n-1}) = 0, ]

which is equivalent to:

[ x_1 \oplus x_2 \oplus \cdots \oplus x_{n-1} = a_1 \oplus a_2 \oplus \cdots \oplus a_n. ]

Your task is to count the number of valid sequences \(b\) (or equivalently, the number of choices for \((x_1, x_2, \ldots, x_{n-1})\) satisfying the above conditions) modulo 998244353.

Note: In the special case where \(n=1\), the sequence \(b\) consists of a single element \(a_1\) and the XOR condition requires \(a_1 = 0\) for the sequence to be valid.

inputFormat

The first line contains an integer \(n\) (the length of sequence \(a\)).

The second line contains \(n\) space-separated integers \(a_1, a_2, \ldots, a_n\) representing the sequence \(a\), which is non-decreasing.

outputFormat

Output a single integer: the number of valid sequences \(b\) modulo 998244353.

sample

1
0

1