Vous êtes à nouveau juge ! Le concours que vous arbitrez inclut le problème suivant :

« Vous disposez d'un triomino en forme de L de chacune des $\frac{4^n-1}{3}$ couleurs différentes. Pavé une grille de $2^n$ par $2^n$ en utilisant chacun de ces triominos de telle sorte qu'il y ait exactement une case vide et que toutes les autres cases soient recouvertes par exactement une case d'un tel triomino. Tous les triominos doivent être utilisés. »

Votre équipe doit écrire un vérificateur pour ce problème. La validation des valeurs d'entrée et du format a déjà été effectuée. On vous donnera un prétendu pavage d'une grille de $2^n$ par $2^n$, où chaque case de la grille est soit $0$, soit un entier positif de $1$ à $\frac{4^n-1}{3}$ représentant l'une des couleurs. Déterminez s'il s'agit bien d'un recouvrement de la grille avec $\frac{4^n-1}{3}$ triominos uniques et un seul espace vide.

Les triominos en forme de L ressemblent à ceci :

Entrée

La première ligne de l'entrée contient un entier unique $n$ ($1 \le n \le 10$), qui est le $n$ de la description.

Chacune des $2^n$ lignes suivantes contient $2^n$ entiers $x$ ($0 \le x \le \frac{4^n-1}{3}$), où $0$ représente un espace vide, et tout nombre positif est un identifiant unique d'un triomino.

Sortie

Affichez un entier unique, qui est $1$ si la grille donnée est recouverte de $\frac{4^n-1}{3}$ triominos uniques et d'un seul espace vide. Sinon, affichez $0$.

Exemples

Entrée 1

2
1 1 2 2
1 3 3 2
4 4 3 5
4 0 5 5

Sortie 1

1

Entrée 2

1
1 1
1 1

Sortie 2

0