Problem
Un champ rectangulaire de taille
n*m est spécifié. Chaque cellule contient un entier non négatif. Vous devez compter le nombre de chemins de la cellule (1,1) à la cellule (
n,
m) qui satisfont le conditions suivantes.
1) À partir de chaque cellule, vous ne pouvez que vous déplacer
vers le bas ou
vers la droite sans quitter le champ.
2) Le
OR exclusif au niveau du bit de tous les nombres du chemin doit être égal à
k.
Trouvez le nombre de chemins correspondants pour le champ donné.
Entrée
La première ligne contient trois entiers
n,
m et
k (1 <= n, m <= 20, 0 <= k <= 10
18) - la hauteur et la largeur du champ, et le nombre
k.
Les lignes
n suivantes contiennent des entiers
m ai,j, où
j - le ème élément de
i-ème ligne est égal à
ai,j (0 <= a
i,j < ;= 10
18).
Mentions légales
Imprimer un entier - le nombre de chemins qui satisfont toutes les conditions.
Exemples
| # |
Entrée |
Sortie |
| 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 |