정사각형 모양의 판 위에 세 종류의 표시가 놓여 있다.

각 위치는 비어 있을 수도 있고, 잘라낼 때 기준이 되는 표시가 있을 수도 있으며, 반드시 따로 보존되어야 하는 표시가 있을 수도 있다.

이 판을 여러 조각으로 나누어, 최종적으로 얻어지는 모든 조각이 다음 조건을 만족하게 하려고 한다.

• 기준이 되는 표시는 조각 안에 남아 있으면 안 된다.

• 보존되어야 하는 표시는 각 조각마다 정확히 하나씩만 있어야 한다.

판을 자를 때에는 반드시 기준이 되는 표시가 놓인 위치를 지나는 직선으로 잘라야 한다.

또한 판의 방향 때문에 자르는 선은 가로 방향 또는 세로 방향이어야 한다.

다만, 같은 조각을 계속 나누어 가는 과정에서 직전에 사용한 방향과 같은 방향으로는 다시 자를 수 없다.

처음 자를 때에는 가로 방향과 세로 방향 중 어느 쪽도 사용할 수 있다.

자를 때에는 다음 조건도 만족해야 한다.

• 자른 결과는 반드시 두 개의 조각으로 나뉘어야 한다.

• 보존되어야 하는 표시가 있는 위치를 지나는 선으로는 자를 수 없다.

• 최종적으로 남은 조각 하나에 보존되어야 하는 표시가 두 개 이상 들어 있으면 안 된다.

여기서 방향 제한은 전체 절단 순서만을 뜻하는 것이 아니다.

어떤 조각이 잘려 나온 뒤, 그 조각을 다시 자를 때 바로 이전에 그 조각을 만들 때 사용된 방향과 같은 방향으로 자를 수 없다는 뜻이다.

판의 상태가 주어졌을 때, 위 조건을 모두 만족하도록 판을 나누는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 판의 크기 N이 들어온다.

다음 줄부터 N줄에 걸쳐 판의 상태가 입력으로 들어온다.

각 칸의 값은 다음을 의미한다.

• 0: 아무 표시도 없는 위치

• 1: 자를 때 기준이 되는 표시

• 2: 최종 조각에 하나씩 포함되어야 하는 표시

각 줄에 주어지는 판의 정보는 공백 하나로 구분한다.

보존되어야 하는 표시의 수는 15개를 넘지 않는다.

출력

각 조각 안에 기준이 되는 표시가 없고, 보존되어야 하는 표시가 정확히 하나만 있도록 판을 나누는 방법의 수를 출력한다.

가능한 경우가 존재하지 않으면 -1을 출력한다.

제한

• 1 ≤ N ≤ 20

예제 입력 1

8
0 0 0 0 0 2 0 0
0 0 0 0 0 0 1 0
0 0 2 1 0 0 2 0
0 1 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 2 1 0 0 0
0 0 0 0 0 0 2 0
0 0 0 0 0 0 0 0

예제 출력 1

1

예제 입력 2

5
0 0 0 0 0
0 2 2 0 0
0 1 1 1 0
0 2 1 2 0
2 0 0 0 0

예제 출력 2

-1