문제
p를 {1, 2,..., n}으로 구성된 모든 순열의 조합이라고 가정하자. N x N의 행렬 A가 주어졌을 때
A[1][p[1]] * A[2][p[2]] * ... * A[n][p[n]] 의 모든 합을 구하는 프로그램을 작성하라.
가령 3 x 3의 행렬이 다음과 같이 주어졌다고 가정하자.
위의 경우 모든 순열에 대한 A[1][p[1]] * A[2][p[2]] * A[3][p[3]] 의 곱들의 합은 다음과 같다.
A[1][1] * A[2][2] * A[3][3] +
A[1][1] * A[2][3] * A[3][2] +
A[1][2] * A[2][1] * A[3][3] +
A[1][2] * A[2][3] * A[3][1] +
A[1][3] * A[2][1] * A[3][2] +
A[1][3] * A[2][2] * A[3][1] = 1*5*9 + 1*6*8 + 2*4*9 + 2*6*7 + 3*4*8 + 3*5*7 = 450
입력
입력의 첫줄에는 배열의 크기 N(1<=N<=16) 이 입력되며, 그 다음 N줄마다 N개의 행렬의 원소가 입력된다.
각각의 원소는 빈칸으로 구분되며, 행렬의 원소의 크기는 0 보다 크고 10,000 보다 작은 정수로 이루어져 있다.
출력
입력에 대한 합의 마지막 4자리만 출력한다.
다시 말해서 합이 99999 일 경우 9999를 출력하면 된다.
예제1
입력
3
123
456
789
출력
450