Problem
Um campo retangular de tamanho
n*m é especificado. Cada célula contém um inteiro não negativo. Você precisa contar o número de caminhos da célula (1,1) para a célula (
n,
m) que satisfazem o seguintes condições.
1) De cada célula, você só pode mover
para baixo ou
para a direita sem sair do campo.
2) O bit a bit exclusivo
OU de todos os números no caminho deve ser igual a
k.
Encontre o número de caminhos correspondentes para o campo fornecido.
Entrada
A primeira linha contém três inteiros
n,
m e
k (1 <= n, m <= 20, 0 <= k <= 10
18) - a altura e a largura do campo e o número
k.
Cada uma das seguintes
n linhas contém
m inteiros
ai,j, onde
j -ésimo elemento de
i-ésima linha é igual a
ai,j (0 <= a
i,j < ;= 1018).
Impressão
Imprima um inteiro - o número de caminhos que satisfazem todas as condições.
Exemplos
| # |
Entrada |
Saída |
| 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 |