Задано прямоугольное поле размера \(n \times m\). В каждой клетке записано целое число; число, записанное в клетке (\(i, j\)) равно \(a_{i, j}\). Ваша задача — посчитать количество путей из клетки (\(1, 1\)) в клетку (\(n, m\)), удовлетворяющих следующим условиям:
Найдите количество подходящих путей для заданного поля.
Первая строка входных данных содержит три целых числа \(n\), \(m\) и \(k\) (\(1 \le n, m \le 20\), \(0 \le k \le 10^{18}\)) — высота и ширина поля, и число \(k\).
Следующие \(n\) строк содержат по \(m\) целых чисел каждая, где \(j\)-й элемент \(i\)-й строки равен \(a_{i, j}\) (\(0 \le a_{i, j} \le 10^{18}\)).
Выведите одно целое число — количество путей из (\(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
3 4 1000000000000000000 1 3 3 3 0 3 3 2 3 0 1 1
0
3000 ms 256 Mb Правила оформления программ и список ошибок при автоматической проверке задач