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ć?</p>

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.

입력 형식

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

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.

출력 형식

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

예제 입력

2
0 0
0 0
0 0

예제 출력

5