XOR-шляхи#8574
Дано прямокутне поле розміру n \times m. У кожній клітинці записано ціле число; число, записане в клітинці , дорівнює a_{i, j}. Ваше завдання — порахувати кількість шляхів з клітинки у клітинку , які задовольняють таким умовам:
• З клітинки можна рухатися лише вниз або вправо. Більш формально, з клітинки можна переміститися у клітинку (i, j + 1) або в клітинку (i + 1, j). Клітинка, у яку здійснюється переміщення, не може перебувати за межами поля.
• Xor всіх чисел на шляху з клітинки у клітинку має дорівнювати .
Знайдіть кількість відповідних шляхів для заданого поля.
Перший рядок містить три цілих числа , і (1 \leq n, m \leq 20, 0 \leq k \leq 10^{18}) — висота й ширина поля, а також число .
Наступні рядків містять по цілих чисел кожна, де -й елемент -го рядка дорівнює a_{i, j} (0 \leq a_{i, j} \leq 10^{18}).
Виведіть одне ціле число — кількість шляхів з у , у яких xor всіх чисел на шляху дорівнює .
Приклад 1
Приклад 2