Klocki powracają

Limit pamięci: 32 MB

Bajtazar korzystając z programu komputerowego opanował już do perfekcji sposoby przekładania klocków między szufladami. Niestety okazuje się, że znalazło się wiele innych osób, które również to potrafią. Musi więc wymyślić bardziej skomplikowaną sztuczkę, by przyciągnąć uwagę Bajtoliny.

Tym razem Bajtazar ma do dyspozycji klocków ponumerowanych liczbami . Ponadto posiada planszę o rozmiarach . Niektóre klocki układa na planszy, po jednym klocku na polu. Teraz zastanawia się na ile różnych sposobów może rozłożyć pozostałe klocki na polach, tak by w każdym wierszu i każdej kolumnie klocki uporządkowane były w rosnącej kolejności numerów.

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia rozmiar planszy i rozmieszczenie klocków które już są rozłożone na polach,
• wyznaczy ilość możliwych rozmieszczeń pozostałych klocków na planszy,
• wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu znajduje się jedna liczba całkowita (). W kolejnych dwóch liniach znajduje się opis planszy. Każda z nich składa się z ciągu liczb całkowitych (). Zero oznacza, że na danym polu nie ma żadnego klocka. Liczba dodatnia to numer klocka umieszczonego na danym polu. Każdy klocek jest umieszczony na planszy co najwyżej raz.

Wyjście

Wypisz jedną liczbę całkowitą - ilość rozmieszczeń pozostałych klocków na planszy. Numery klocków w każdym wierszu i każdej kolumnie muszą być rosnące (patrząc odpowiednio w prawo i w dół).

Przykład

Dla danych wejściowych:

3
0 3 0
2 0 0

poprawną odpowiedzią jest:

2

Autor zadania: Krzysztof Diks.