Вам даны два положительных целых числа \(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\) обозначает операцию побитового исключающего ИЛИ.
Выходные данные
Для каждого набора входных данных выведите сумму всех возможных значений \(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\).
Примечание
В первом наборе входных данных у нас должно быть \(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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
69 1
5 2
0 10
420 69
12 26
73 34
1000000000000000000 10
|
69
6
0
44310
42
1369
216734648
|