Вам дан массив целых чисел \(a_1, a_2, \ldots, a_n\) и целое число \(x\).
Найдите количество непустых подмножеств индексов этого массива \(1 \leq b_1 < b_2 < \ldots < b_k \leq n\) таких, что для всех пар \((i, j)\), где \(1 \leq i < j \leq k\), выполняется неравенство \(a_{b_i} \oplus a_{b_j} \leq x\). Здесь \(\oplus\) обозначает операцию побитового исключающего ИЛИ. Так как ответ может быть большим, выведите его по модулю \(998\,244\,353\).
Выходные данные
Выведите одно целое число: количество непустых подмножеств таких, что побитовое исключающее ИЛИ любых двух элементов не больше \(x\), по модулю \(998\,244\,353\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 2
0 1 2 3
|
8
|
|
2
|
3 6
4 2 2
|
7
|
|
3
|
4 0
1 1 2 2
|
6
|