F. Xor-пути
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задано прямоугольное поле размера $$$n \times m$$$. В каждой клетке записано целое число; число, записанное в клетке ($$$i, j$$$) равно $$$a_{i, j}$$$. Ваша задача — посчитать количество путей из клетки ($$$1, 1$$$) в клетку ($$$n, m$$$), удовлетворяющих следующим условиям:

  • Из клетки можно перемещаться только вниз или только вправо. Более формально, из клетки ($$$i, j$$$) можно переместиться в клетку ($$$i, j + 1$$$) или в клетку ($$$i + 1, j$$$). Клетка, в которую совершается перемещение, не может находиться за пределами поля.
  • Xor всех чисел на пути из клетки ($$$1, 1$$$) в клетку ($$$n, m$$$) должен быть равен $$$k$$$ (xor это побитовое исключающее ИЛИ, эта операция представлена как '^' в Java или C++ и "xor" в Pascal).

Найдите количество подходящих путей для заданного поля.

Входные данные

Первая строка входных данных содержит три целых числа $$$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
Примечание

Все пути из первого тестового примера:

  • $$$(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3)$$$;
  • $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)$$$;
  • $$$(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3)$$$.

Все пути из второго тестового примера:

  • $$$(1, 1) \rightarrow (2, 1) \rightarrow (3, 1) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$$$;
  • $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (3, 2) \rightarrow (3, 3) \rightarrow (3, 4)$$$;
  • $$$(1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (3, 4)$$$;
  • $$$(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$$$;
  • $$$(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3) \rightarrow (3, 4)$$$.