시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 8 1 1 25.000%

문제

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

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

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

이 게임에서 도미노는 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 사이의 수 (0,9 포함) 또는 A~I사이 (A,I 포함)의 문자가 써 있고, A~I의 문자가 의미하는 것은 -1부터 -9이다.

출력

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

예제 입력

2
35
44

예제 출력

8

힌트

출처