IX Wiosenny Turniej w Programowaniu Zespołowym Politechnika Poznańska, 11.06.2005

Opis

W Patentolandii postanowiono wreszcie pozbyć się niepotrzebnych patentów. Patenty są radioaktywne i nie można ich tak po prostu wyrzucić do śmieci. Patenty trzeba składować w specjalnie przygotowanych do tego studniach. Każda studnia jest prostopadłościanem o podstawie 3 na 3 pola i o głębokości n pól. Natomiast patenty są prostopadłościanami o wymiarach 1x1x2 pola, które przed włożeniem do studni można obracać we wszystkich kierunkach. Zarówno Anty-Patentowcy jak i Anty-Anty-Patentowcy nie chcą, aby miejsce w studni sie marnowało, więc zawsze tak upychają patenty, że studnia jest całkowicie załadowana (każde pole 1x1x1 jest zajęte).

Postanowiono, że Twoje zadanie będzie następujące: Policz na ile różnych sposobów można zapełnić daną studnię patentami. Pytasz po co? Hmm... Rzeczywiście nie ma to wielkiego sensu, ale chodzą słuchy, że jeśli zrobisz to poprawnie i wystarczająco szybko, to dostaniesz "Accepta" (cokolwiek by to znaczyło).

Wejście

W pierwszej linii wejścia znajduje się jedna dodatnia liczba całkowita oznaczająca liczbę następujących zestawów danych.

W pierwszej linii każdego zestawu danych znajdują się 2 liczby całkowite 1≤N≤10000, oznaczająca głębokość studni oraz liczą 1≤M≤200. W następnych 3 liniach znajduje się opis 9 pól podstawy studni. Każde pole opisane jest jedną liczbą. Jeśli liczba ta wynosi 1 oznacza to, że pole to jest zajęte, w przeciwnym wypadku (gdy wynosi 0) oznacza, to że pole jest puste.

Wyjście

Dla każdego zestawu danych należy wypisać jedną liczbę całkowitą X mod M, gdzie X oznaczająca liczbę różnych sposobów, na ile można całkowicie zapełnić studnię o głębokości N i podanym na wejściu zapełnieniu podstawy studni.

Przykładowe wejście

4
1 100
0 0 0
0 1 0
0 0 0
1 100
0 0 0
0 0 0
0 0 0
2 100
0 0 0
1 1 1
1 1 1
2 100
0 1 1
1 1 1
1 1 1

Przykładowe wyjście

2
0
11
4