14255번 - 멋진 배열

크기가 N행 N열인 배열 A와 0부터 N-1까지의 정수로 이루어진 순열 P가 있다.

Sum(A, P) = A[0][P[0]] + A[1][P[1]] + ... + A[N-1][P[N-1]] 이다.

순열 P를 어떻게 고르는지에 상관없이 Sum(A, P)가 항상 같으면 그러한 배열을 멋지다고 한다.

일부 수가 지워진 배열 A가 주어졌을 때, 멋진 배열을 만드는 방법의 수를 구하는 프로그램을 작성하시오. 즉, 지워진 수를 모두 채워 넣는 방법의 수를 구하는 것이다.

첫째 줄에 배열 A의 크기 N (1 ≤ N ≤ 50)이 주어진다.

둘째 줄부터 N개의 줄에는 배열 A가 주어진다. 지워진 수는 '-'로 주어지며, 나머지 수는 모두 0보다 크거나 같고, 9보다 작거나 같은 정수이다.

멋진 배열을 만드는 방법의 수를 1,000,000,007로 나눈 나머지를 출력한다. 항상 답이 무한대가 아닌 경우만 입력으로 주어진다. 또한, 새로 채우는 수는 9보다 커도 된다.