Вы получили подарок на день рождения — \(n\) троек целых чисел! \(i\)-я из них равна \(\lbrace a_{i}, b_{i}, c_{i} \rbrace\). Все числа не меньше \(0\) и строго меньше чем \(2^{k}\), где \(k\) — фиксированное целое число.
Однажды вам надоело играть с этими тройками, и вы выбрали три новых целых числа \(x\), \(y\), \(z\), а затем составили \(n\) массивов. \(i\)-й массив состоит из \(a_i\), повторенного \(x\) раз, \(b_i\), повторенного \(y\) раз и \(c_i\), повторенного \(z\) раз. Таким образом, каждый массив имеет длину \((x + y + z)\).
Вы хотите выбрать ровно одно число из каждого массива так, чтобы их побитовое исключающее ИЛИ (XOR) было равно \(t\). Найдите количество способов так выбрать числа для каждого \(t\) от \(0\) до \(2^{k} - 1\) включительно по модулю \(998244353\).
Выходные данные
Выведите одну строку, содержащую \(2^{k}\) целых чисел. \(i\)-е из них должно быть равно количеству способов выбрать ровно одно число из каждого массива так, чтобы их побитовое исключающее ИЛИ (XOR) было равно \(t = i-1\) по модулю \(998244353\).
Примечание
В первом примере единственный массив равен \((1, 0, 0, 1, 1, 1)\), есть два способа получить \(0\) в результате побитового исключающего ИЛИ и четыре способа получить \(1\).
Во втором примере два массива равны \((0, 1, 1, 2)\) и \((1, 2, 2, 3)\). Всего есть шестнадцать \((4 \cdot 4)\) способов выбрать числа, \(4\) из них (\(1 \oplus 1\) и \(2 \oplus 2\) по два раза) дают \(0\), \(2\) из них (\(0 \oplus 1\) и \(2 \oplus 3\)) дают \(1\), \(4\) из них (\(0 \oplus 2\) и \(1 \oplus 3\) по два раза) дают \(2\), и наконец \(6\) из них (\(0 \oplus 3\), \(2 \oplus 1\) и четыре раза \(1 \oplus 2\)) дают \(3\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
1 1
1 2 3
1 0 1
|
2 4
|
|
2
|
2 2
1 2 1
0 1 2
1 2 3
|
4 2 4 6
|
|
3
|
4 3
1 2 3
1 3 7
0 2 5
1 0 6
3 3 2
|
198 198 126 126 126 126 198 198
|