도미노 게임 2

도미노 하나에는 순서가 있는 두 수가 적혀 있다.

세준이는 가능한 모든 순서쌍 (i, j)에 해당하는 도미노를 하나씩 가지고 있다. 여기서 1 <= i <= N, 1 <= j <= N이므로 도미노는 모두 N^2개이다.

게임에서는 이 도미노들이 N x N 보드에 놓여 있다. i번째 행, j번째 열에는 (i, j)라고 적힌 도미노가 놓여 있다.

플레이어는 도미노를 정확히 N개 골라야 한다. 단, 고른 도미노 중 같은 행에 있는 도미노가 두 개 이상 있으면 안 되고, 같은 열에 있는 도미노가 두 개 이상 있어도 안 된다.

고른 도미노들은 하나 이상의 사이클 그룹으로 나뉜다. 도미노 A의 두 번째 수와 도미노 B의 첫 번째 수가 같으면 A 다음에 B를 둘 수 있고, 마지막 도미노의 두 번째 수가 첫 번째 도미노의 첫 번째 수와 같으면 하나의 사이클이 된다. (i, i)처럼 두 수가 같은 도미노는 혼자서 하나의 사이클 그룹을 이룬다.

각 행과 각 열에서 정확히 하나씩 고르는 조건 때문에, 어떤 선택도 항상 하나 이상의 사이클 그룹으로 나뉜다.

모든 도미노의 뒷면에는 수가 하나씩 적혀 있다. 어떤 선택의 점수는 고른 도미노들의 뒷면 수를 모두 곱한 값이다. 그 선택에서 생긴 사이클 그룹의 개수가 짝수라면 점수에 -1을 한 번 더 곱한다.

도미노 뒷면의 수들이 주어졌을 때, 가능한 모든 선택의 점수 합을 구하라.

첫째 줄에 자연수 N이 주어진다. N은 100 이하이다.

다음 N개의 줄에는 도미노 뒷면에 적힌 수가 주어진다. i번째 줄의 j번째 문자는 도미노 (i, j)의 뒷면에 적힌 수를 뜻한다.

각 문자는 0부터 9까지의 숫자이거나 A부터 I까지의 대문자이다. A부터 I까지는 차례대로 -1부터 -9까지를 뜻한다.

첫째 줄에 가능한 모든 선택의 점수 합을 121547로 나눈 나머지를 출력한다.