XOR-пути
XOR-пути
Дано прямоугольное поле размера n × m. В каждой клетке записано целое число; число, записанное в клетке (i, j) равно ai,j
. Ваша задача - вычислить количество путей из клетки (1,1) в клетку (n, m), удовлетворяющих следующим условиям:
• Из клетки можно перемещаться только вниз или только вправо. Более формально, из клетки (i, j) можно переместиться в клетку (i, j + 1) или в клетку (i + 1, j). Клетка, в которую производится перемещение, не может находиться за границами поля.
• Xor всех чисел на пути из клетки (1,1) в клетку (n, m) должно равняться k.
Найдите количество соответствующих путей для заданного поля.
Входные данные
Перший рядок містить три цілих числа n, m і k (1 ≤ n, m ≤ 20, 0 ≤ k ≤ 1018
) - висота і ширина поля, і число k.
Наступні n рядків містять по m цілих чисел кожна, де j-й елемент i-го рядка дорівнює
ai,j
(0 ≤ ai,j
≤ 1018
).
Выходные данные
Виведіть одне ціле число - кількість шляхів з (1,1) в (n, m) з xor всіх чисел на шляху рівним k.
3 3 11 2 1 5 7 10 0 12 6 4
3
3 4 2 1 3 3 3 0 3 3 2 3 0 1 1
5