Runda 3: Magiczny prostokąt

Limit czasu: 2s,  limit pamięci: 64MB

Dany jest prostokąt o trzech wierszach i N kolumnach. Chcemy wpisać w pola tego prostokąta liczby od 1 do 3N tak, żeby w każdym wierszu oraz w każdej kolumnie wpisane liczby tworzyły ciąg rosnący. Na ile sposobów można to zrobić?

Niektore pola prostokąta mogą być już ustalone. Poniewaz liczba możliwych uzupełnień może być duża, wystarczy wypisać jej resztę z dzielenia przez 1000007.

Wejście

W pierwszej linii znajduje się jedna liczba naturalna N (1 <= N <= 200).

Następnie w 3 kolejnych liniach, z których każda zawiera N liczb a_i,j (0 <= a_i,j <= 3N), znajduje się opis prostokąta wypisany wierszami (kolejne wiersze wypisane są od lewej do prawej). Liczba a_i,j równa 0 oznacza, że liczba w odpowiadającym polu prostokąta jest nieustalona. W p.p. liczba w odpowiadającym polu wynosi a_i,j.

Wyjście

Opisana w treści liczba możliwych uzupełnień, modulo 1000007.

Przykład