J. Zero-XOR Array
time limit per test
6 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array of integers $$$a$$$ of size $$$n$$$. This array is non-decreasing, i. e. $$$a_1 \le a_2 \le \dots \le a_n$$$.

You have to find arrays of integers $$$b$$$ of size $$$2n - 1$$$, such that:

  • $$$b_{2i-1} = a_i$$$ ($$$1 \le i \le n$$$);
  • array $$$b$$$ is non-decreasing;
  • $$$b_1 \oplus b_2 \oplus \dots \oplus b_{2n-1} = 0$$$ ($$$\oplus$$$ denotes bitwise XOR operation: https://en.wikipedia.org/wiki/Exclusive_or. In Kotlin, it is xor function).

Calculate the number of arrays that meet all the above conditions, modulo $$$998244353$$$.

Input

The first line contains a single integer $$$n$$$ ($$$2 \le n \le 17$$$) — the size of the array $$$a$$$.

The second line contains $$$n$$$ integers ($$$0 \le a_i \le 2^{60} - 1; a_i \le a_{i+1}$$$) — elements of the array $$$a$$$.

Output

Print a single integer — the number of arrays that meet all the above conditions, modulo $$$998244353$$$.

Examples
Input
3
0 1 3
Output
2
Input
4
0 3 6 7
Output
6
Input
5
1 5 9 10 23
Output
20
Input
10
39 62 64 79 81 83 96 109 120 122
Output
678132