Это произошло 18 октября 2017 года. Shohag, меланхоличная душа, твердо решил, что будет серьезно заниматься спортивным программированием, поскольку оно показалось ему увлекательным. Прошло 4 года, и он счастлив, что выбрал этот путь. Сейчас он создает раунд на Codeforces. Он нашел выдающуюся задачу, но не имеет ни малейшего представления о том, как ее решить. Помогите ему решить финальную задачу раунда.
Вам даны три целых числа \(n\), \(k\) и \(x\). Найдите количество, по модулю \(998\,244\,353\), последовательностей целых чисел \(a_1, a_2, \ldots, a_n\) таких, что выполняются следующие условия:
- \(0 \le a_i \lt 2^k\) для каждого целого числа \(i\) от \(1\) до \(n\).
- Не существует непустой подпоследовательности в \(a\) такой, что побитовое исключающее ИЛИ элементов подпоследовательности равно \(x\).
Последовательность \(b\) является подпоследовательностью последовательности \(c\), если \(b\) может быть получена из \(c\) путем удаления нескольких (возможно, нуля или всех) элементов.
Выходные данные
Для каждого набора входных данных выведите одно целое число — ответ на задачу.
Примечание
В первом наборе входных данных допустимыми последовательностями являются \([1, 2]\), \([1, 3]\), \([2, 1]\), \([2, 3]\), \([3, 1]\) и \([3, 2]\).
Во втором наборе входных данных единственной допустимой последовательностью является \([0, 0]\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
2 2 0
2 1 1
3 2 3
69 69 69
2017 10 18
5 7 0
|
6
1
15
699496932
892852568
713939942
|