D. Подсчёт XOR
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам даны два положительных целых числа $$$n$$$ и $$$m$$$. Найдите сумму всех возможных значений $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$$$, где $$$a_1,a_2,\ldots,a_m$$$ являются неотрицательными целыми числами такими, что $$$a_1+a_2+\ldots+a_m=n$$$.

Обратите внимание, что все возможные значения $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$$$ должны быть посчитаны в сумме ровно один раз.

Так как ответ может быть очень большим, выведите его по модулю $$$998244353$$$.

Здесь $$$\bigoplus$$$ обозначает операцию побитового исключающего ИЛИ.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит единственное целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая и единсвственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$0\le n\le 10^{18}, 1\le m\le 10^5$$$) — сумма и количество чисел в наборе, соответственно.

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

Для каждого набора входных данных выведите сумму всех возможных значений $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_m$$$ по всем наборам неотрицательных целых чисел $$$a_1,a_2,\ldots,a_m$$$ с $$$a_1+a_2+\ldots+a_m=n$$$. Так как ответ может быть очень большим, выведите его по модулю $$$998244353$$$.

Пример
Входные данные
7
69 1
5 2
0 10
420 69
12 26
73 34
1000000000000000000 10
Выходные данные
69
6
0
44310
42
1369
216734648
Примечание

В первом наборе входных данных у нас должно быть $$$a_1=69$$$, поэтому это единственное возможное значение $$$a_1$$$, следовательно, наш ответ — $$$69$$$.

Во втором наборе входных данных $$$(a_1,a_2)$$$ может быть равно $$$(0,5), (1,4), (2,3), (3,2), (4,1)$$$ или $$$(5,0)$$$, в которых $$$a_1\bigoplus a_2$$$ равно $$$5,5,1,1,5,5$$$ соответственно. Поэтому $$$a_1\bigoplus a_2$$$ может быть равно $$$1$$$ или $$$5$$$, поэтому ответ равен $$$1+5=6$$$.

В третьем наборе входных данных $$$a_1,a_2,\ldots,a_{10}$$$ должны быть все равны $$$0$$$, поэтому $$$a_1\bigoplus a_2\bigoplus\ldots\bigoplus a_{10}=0$$$. Поэтому ответ равен $$$0$$$.