Вам задан массив целых чисел \(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\).
Выходные данные
Выведите одно целое число — количество массивов, удовлетворяющих всем вышеописанным условиям, взятое по модулю \(998244353\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
0 1 3
|
2
|
|
2
|
4
0 3 6 7
|
6
|
|
3
|
5
1 5 9 10 23
|
20
|
|
4
|
10
39 62 64 79 81 83 96 109 120 122
|
678132
|