Вам дан массив из n k-битных чисел a[1]
, a[2]
, ..., a[n]
. Ваша задача посчитать
Операция a + b обозначает операцию побитовое исключающее "ИЛИ" чисел a и b. Так как ответ может быть большим, выведите его по модулю 998 244 353.
В первой строке записаны три целых числа n, k, x (1 ≤ n, k, n * k ≤ 300 000, 1 ≤ x ≤ 3) - длина массива, количество бит в числах, и степень, в которую возводятся значенияисключающих "ИЛИ".
В следующих n строках записаны элементы массива. В i-ой из них записана строка s[0]
, s[1]
, ..., s[k-1]
, состоящая из "0" и "1". Тогда
Выведите одно число - остаток от деления суммы x-ых степеней исключающих "ИЛИ" по всем парам чисел в массиве на 998 244 353.
В первом тесте в массиве содержатся числа [5, 4, 4], а искомая сумма равна соответственно (5 xor 4) + (5 xor 4) + (4 xor 4) = 1 + 1 + 0 = 2.
Во втором тесте в массиве содержатся числа [61, 38], а искомая сумма равна (61 xor 38) ^ 3 = 27^3
= 19683.