Problem
Se especifica un campo rectangular de tamaño
n*m. Cada celda contiene un número entero no negativo. Necesita contar el número de rutas desde la celda (1,1) a la celda (
n,
m) que satisfacen el siguientes condiciones.
1) Desde cada celda, solo puedes mover
abajo o
derecha sin salir del campo.
2) El
OR exclusivo bit a bit de todos los números en la ruta debe ser igual a
k.
Encuentre el número de rutas coincidentes para el campo dado.
Entrada
La primera línea contiene tres números enteros
n,
m y
k (1 <= n, m <= 20, 0 <= k <= 10
18) - la altura y el ancho del campo, y el número
k.
Las siguientes líneas
n contienen cada una
m enteros
ai,j, donde
j -th elemento de
i-th fila es igual a
ai,j (0 <= a
i,j <= 1018).
Impresión
Imprime un número entero: el número de rutas que satisfacen todas las condiciones.
Ejemplos
| # |
Entrada |
Salida |
| 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 |