Задано прямоугольное поле размера
n*m. В каждой клетке записано целое неотрицательное число. Требуется посчитать количество путей из клетки (1,1) в клетку (
n,
m), удовлетворяющих следующим условиям.
1) Из каждой клетки можно перемещаться только
вниз или
вправо, не выходя при этом за пределы поля.
2) Побитовое исключающее
ИЛИ всех чисел на пути должно быть равно
k.
Найдите количество подходящих путей для заданного поля.
Входные данные
Первая строка содержит три целых числа
n,
m и
k (1 <= n, m <= 20, 0 <= k <= 10
18) - высота и ширина поля, и число
k.
Следующие
n строк содержат по
m целых чисел
ai,j, где
j-й элемент
i-й строки равен
ai,j (0 <= a
i,j <= 10
18).
Выходные данные
Выведите одно целое число - количество путей, удовлетворяющих всем условиям.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
3 3 11
2 1 5
7 10 0
12 6 4 |
3 |
| 2 |
3 4 2
1 3 3 3
0 3 3 2
3 0 1 1 |
5 |