Sześciany [A]
Limit pamięci: 64 MB
Bajtazar wymyślił nowy system podpisu półelektronicznego BajtoKrypt, w którym
każdy użytkownik do podpisywania dokumentów wykorzystuje swój klucz, będący
pustym w środku sześcianem o boku długości .
Każda ścianka każdego sześcianu jest podzielona na kratek,
z których każda może zawierać jeden chip (szyfrujący albo ogólnego
przeznaczenia) albo być pusta.
Wszystkie chipy szyfrujące są identyczne; podobnie każde dwa
chipy ogólnego przeznaczenia są takie same.
Układ chipów szyfrujących na każdej ściance każdego sześcianu
jest z dokładnością do obrotu zawsze taki sam (dla każdej ścianki każdego
sześcianu istnieje taki sposób jej obrotu, żeby układy
chipów szyfrujących wszystkich ścianek wyglądały dokładnie tak samo);
jedyne, czym mogą różnić się
ścianki to to, które z pozostałych kratek są zajęte przez chipy
ogólnego przeznaczenia.
Ponadto wszystkie chipy są zawsze umieszczane po jednej stronie ścianki
- dokładniej tej, która jest skierowana do środka sześciennego klucza.
Bajtohaker zamierza złamać system BajtoKrypt; nauczył się już idealnie
podrabiać sześcienne klucze.
Chciałby on wiedzieć, ile minimalnie kluczy potrzebuje, by móc
podszyć się pod dowolnego użytkownika systemu.
Dokładniej, dla każdego możliwego klucza użytkownika (określonego przez
rozmieszczenie chipów ogólnego przeznaczenia na każdej ze ścianek i wzajemne
ułożenie ścianek w ramach klucza) Bajtohaker chciałby mieć w swoim
zbiorze kluczy taki, który po ewentualnym rozmontowaniu na pojedyncze ścianki,
poprzekładaniu ich i poobracaniu w dowolny sposób, a następnie zmontowaniu
z powrotem daje w rezultacie sześcian identyczny z rozważanym kluczem użytkownika.
Dwa klucze uznajemy przy tym za identyczne, jeżeli można w taki sposób
poobracać jeden z nich, aby otrzymać drugi.
Żeby nie przygnębiać Bajtohakera, odpowiedź dla jego problemu podaj modulo .
Zadanie
Napisz program, który:
- wczyta ze standardowego wejścia długość boku każdego z sześciennych kluczy
i opis rozmieszczenia chipów szyfrujących na każdej ze ścianek,
- obliczy minimalną liczność zbioru kluczy, który spełni wymaganie Bajtohakera,
- wypisze resztę z dzielenia wyniku przez na standardowe wyjście.
Wejście
W pierwszym wierszu wejścia znajduje się jedna liczba całkowita dodatnia ().
W kolejnych wierszach znajduje się po liczb całkowitych (),
pooddzielanych pojedynczymi odstępami.
oznacza, że w -tej kratce -tego wiersza każdej ścianki
znajduje się chip szyfrujący.
oznacza, że kratka ta nie zawiera chipu szyfrującego, czyli
może być pusta bądź wykorzystana na chip ogólnego przeznaczenia.
Wyjście
W jedynym wierszu wyjścia powinna znajdować się jedna liczba całkowita -
liczba kluczy potrzebnych Bajtohakerowi modulo .
Przykład
Dla danych wejściowych:
3
1 0 0
1 1 1
0 0 1
poprawną odpowiedzią jest:
5005
Autor zadania: Krzysztof Dulęba.