1556번 - 도미노2

도미노는 위와 같이 생겼다.

세준이가 가지고 있는 도미노는 약간 다르다. 세준이는 도미노를 N²개 가지고 있다. 따라서 N=2라면, 세준이는 (1,1), (1,2), (2,1), (2,2) 이렇게 총 N²개를 가지고 있는 것이다.

세준이는 이 도미노를 가지고 도미노미도마도라는 게임을 하려고 한다. 이 게임은 김민오가 만들었다.

이 게임에서 도미노는 N*N크기의 보드에 놓여져 있다. i번째 행, j번째 열에는 (i,j)라고 쓰여 있는 도미노가 놓여져 있다. 플레이어는 도미노를 정확하게 N개를 골라야 하는데, 선택한 도미노를 두 개가 같은 행에서 고르고, 선택한 도미노를 같은 열에서 고르면 안 된다는 조건이 있다. 또, 고른 도미노를 가지고 사이클을 만들 수 있다. 사이클을 만드는 방법은, 도미노 A와 B가 있을 때, A의 두 번째 숫자와 B의 첫 번째 수가 같으면 된다. 그리고 사이클을 이루는 첫 번째 도미노의 처음 숫자와 마지막 도미노의 둘째 숫자가 같으면 된다.

예를 들어, (1,3), (3,2), (2,4), (4,1)을 골라서 사이클을 만들 수 있다.

N개의 도미노를 고르면 이러한 사이클이 한 개 또는 그 이상의 그룹이 나온다. (1,1)와 같은 도미노는 자기 자신으로 사이클을 이루므로 하나의 그룹이다.

게임의 조건 중에 각 행과 열에서 중복되면 안되는 조건이 있기 때문에, 항상 사이클을 이룰 수 있다.

모든 도미노는 그 뒷면에 숫자가 쓰여 있다. 이 게임에서 점수를 계산할 때는 자기가 고른 도미노의 뒷면에 쓰여 있는 수를 모두 곱한다. 그 다음에 만약 사이클 그룹의 개수가 짝수가 되면 그 수에 -1을 곱한다.

도미노의 개수와 도미노 뒷면에 쓰여 있는 수가 주어질 때, 세준이가 얻을 수 있는 가능한 모든 점수의 합을 구하는 프로그램을 작성하시오.

첫째 줄에 N이 주어진다. N은 100보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 각 도미노에 쓰여 있는 수가 주어진다. i행 j열에 쓰여 있는 수는 도미노 (i,j)의 뒷 면에 쓰여 있는 수이다. 도미노의 뒷면에는 0부터 9까지의 수와 A부터 I까지 알파벳 대문자가 쓰여 있고, A부터 I까지 문자가 의미하는 것은 -1부터 -9까지이다.

첫째 줄에 세준이가 얻을 수 있는 모든 점수의 합을 121547로 나눈 나머지를 출력한다.