Wieże

Limit pamięci: 32 MB

Bajtocki Uniwersytet imienia Bajtazara Gąbki zaczął ostatnio odnosić poważne sukcesy w programowaniu zespołowym. Jego czołowa drużyna - Bajtockie Sępy - w szybkim tempie zdobyła mistrzostwo wszechświata w tej elitarnej dziedzinie. Nie dosyć, że wygrywała ona wszystkie rundy eliminacyjne, to jeszcze na każdym etapie konkursu rozwiązywała zadania na długo przed upływem dostępnego czasu (standardowe 5 godzin). Aby nie nudzić się w czasie, gdy pozostali zawodnicy usiłowali jeszcze rozwiązać jakieś problemy, przez które oni już dawno przebrnęli, Bajtockie Sępy wymyśliły dla rozrywki następującą grę:

Jeden z zawodników bierze kwadratową szachownicę o wymiarach i usuwa z niej (zakrywa) niektóre pola. Drugi z zawodników ma za zadanie ustawić na szachownicy dokładnie wież, przy czym muszą być spełnione następujące warunki:

• wieże można ustawić tylko na polach, które nie zostały usunięte,
• na każdym polu może stać co najwyżej jedna wieża,
• żadne dwie wieże nie mogą się szachować (tzn. w każdym wierszu i w każdej kolumnie musi stać dokładnie jedna wieża).

Ponieważ ta forma gry była dla mistrzów świata zdecydowanie za prosta, zmodyfikowali ją w następujący sposób: dwaj członkowie drużyny, zamiast ustawiać wieże, muszą obliczyć na ile sposobów można ustawić wieże na szachownicy zgodnie z powyższymi zasadami. Liczba ta może być oczywiście bardzo duża - na przykład, na szachownicy, z której nie usunięto żadnych pól, wieże można ustawić na sposobów - jednak co to za problem dla mistrzów świata. Wszystkie obliczenia wykonują oni oczywiście w pamięci, a grę wygrywa ten z graczy, który szybciej poda prawidłową odpowiedź.

Ty prawdopodobnie nie jesteś jeszcze mistrzem świata, więc twoje zadanie będzie łatwiejsze. Wystarczy, że napiszesz program, który stwierdzi, czy liczba sposobów rozstawień wież jest parzysta, czy nieparzysta.

Zadanie

Napisz program, który:

• wczyta opis szachownicy,
• wyznaczy resztę z dzielenia przez liczby sposobów, na jakie można rozstawić wież na danej szachownicy,
• wypisze wynik.

Wejście

W pierwszym wierszu zapisana jest jedna dodatnia liczba całkowita - liczba przypadków do rozpatrzenia, . Następnie znajduje się opis szachownic, z których każdy wygląda następująco:
W pierwszym wierszu opisującym daną szachownicę znajduje się liczba naturalna - długość i szerokość szachownicy, . W kolejnych wierszach znajdują się opisy kolejnych wierszy szachownicy. W każdym z tych wierszy znajduje się liczb należących do zbioru , pooddzielanych pojedynczymi odstępami. Liczba oznacza, że dane pole zostało usunięte, natomiast , że na danym polu można ustawić wieżę.

Wyjście

Twój program powinien wypisać liczb całkowitych, każdą w osobnym wierszu. Wiersz -ty powinien zawierać dokładnie jedną liczbę - lub - resztę z dzielenia przez liczby sposobów rozstawienia wież na -tej szachownicy, zgodnie z warunkami zadania.

Przykład

2
3
1 1 1
1 1 0
1 0 1
3
1 0 0
0 1 0
0 0 1

1
1

Ilustracja wszystkich możliwości ustawienia wież w pierwszym z przypadków:

Autor zadania: Michał Adamaszek.