Задано прямоугольное поле размера \(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).
Найдите количество подходящих путей для заданного поля.
Выходные данные
Выведите одно целое число — количество путей из (\(1, 1\)) в (\(n, m\)) с xor всех чисел на пути равным \(k\).
Примечание
Все пути из первого тестового примера:
- \((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)\).
Примеры
| № | Входные данные | Выходные данные |
|
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
|
|
3
|
3 4 1000000000000000000
1 3 3 3
0 3 3 2
3 0 1 1
|
0
|