XOR cəmi

Sizə a[1], a[2], ..., a[n] kimi n ədəd k-bitlik ədədlərdən ibarət bir massiv verilib. Sizin vəzifəniz aşağıdakı ifadəni hesablamaqdır:

Burada a + b əməliyyatı, a və b ədədlərinin bit-bitə istisna və ya "XOR" əməliyyatını ifadə edir. Cavabın çox böyük ola biləcəyini nəzərə alaraq, onu 998 244 353 moduluna görə çıxarın.

Giriş məlumatları

Birinci sətirdə üç tam ədəd n, k, x verilir (1 ≤ n, k, n * k ≤ 300 000, 1 ≤ x ≤ 3). Bunlar müvafiq olaraq massiv uzunluğu, ədədlərdəki bitlərin sayı və istisna "XOR" dərəcəsidir.

Növbəti n sətirdə massiv elementləri verilir. i-ci sətirdə s[0], s[1], ..., s[k-1] simvollarından ibarət bir sətir verilir. Bu simvollar yalnız "0" və "1" ola bilər. Belə ki,

Çıxış məlumatları

Bütün cüt ədədlər üçün istisna "XOR" dərəcələrinin cəminin 998 244 353 moduluna görə qalıqını çıxarın.

İzah

Birinci testdə massivdə [5, 4, 4] ədədləri var və axtarılan cəm belədir: (5 xor 4) + (5 xor 4) + (4 xor 4) = 1 + 1 + 0 = 2.

İkinci testdə massivdə [61, 38] ədədləri var və axtarılan cəm belədir: (61 xor 38) ^ 3 = 27^3 = 19683.