F. 18 октября 2017
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это произошло 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$$$ путем удаления нескольких (возможно, нуля или всех) элементов.

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

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^5$$$) — количество наборов входных данных.

Первая и единственная строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$k$$$ и $$$x$$$ ($$$1 \le n \le 10^9$$$, $$$0 \le k \le 10^7$$$, $$$0 \le x \lt 2^{\operatorname{min}(20, k)}$$$), разделенных пробелами.

Гарантируется, что сумма $$$k$$$ по всем наборам входных данных не превышает $$$5 \cdot 10^7$$$.

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

Для каждого набора входных данных выведите одно целое число — ответ на задачу.

Пример
Входные данные
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
Примечание

В первом наборе входных данных допустимыми последовательностями являются $$$[1, 2]$$$, $$$[1, 3]$$$, $$$[2, 1]$$$, $$$[2, 3]$$$, $$$[3, 1]$$$ и $$$[3, 2]$$$.

Во втором наборе входных данных единственной допустимой последовательностью является $$$[0, 0]$$$.