J. Массив с нулевым XOR
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам задан массив целых чисел $$$a$$$ размера $$$n$$$. Данный массив не убывающий, т.е. $$$a_1 \le a_2 \le \dots \le a_n$$$.

Вам необходимо найти массивы целых чисел $$$b$$$ размера $$$2n - 1$$$, таких что:

  • $$$b_{2i-1} = a_i$$$ ($$$1 \le i \le n$$$);
  • массив $$$b$$$ не убывающий;
  • $$$b_1 \oplus b_2 \oplus \dots \oplus b_{2n-1} = 0$$$ ($$$\oplus$$$ обозначает операцию побитового исключающего ИЛИ: https://ru.wikipedia.org/wiki/Исключающее_«или». В языке Kotlin — функция xor).

Посчитайте количество массивов, удовлетворяющих всем вышеописанным условиям, взятое по модулю $$$998244353$$$.

Входные данные

В первой строке задано единственное целое число $$$n$$$ ($$$2 \le n \le 17$$$) — размер массива $$$a$$$.

Вторая строка содержит $$$n$$$ целых чисел ($$$0 \le a_i \le 2^{60} - 1; a_i \le a_{i+1}$$$) — элементы массива $$$a$$$.

Выходные данные

Выведите одно целое число — количество массивов, удовлетворяющих всем вышеописанным условиям, взятое по модулю $$$998244353$$$.

Примеры
Входные данные
3
0 1 3
Выходные данные
2
Входные данные
4
0 3 6 7
Выходные данные
6
Входные данные
5
1 5 9 10 23
Выходные данные
20
Входные данные
10
39 62 64 79 81 83 96 109 120 122
Выходные данные
678132