행사 진행자 하린이는 \(N\) 명의 손님을 \(N\) 개의 좌석에 한 명씩, 빈 좌석 없이 모두 앉히려 한다. 그런데 손님마다 앉을 수 있는 좌석이 정해져 있다.

\(i\) 번째 손님이 \(j\) 번째 좌석에 앉을 수 있는지 여부가 \(N \times N\) 표로 주어진다. 모든 손님이 자신이 앉을 수 있는 좌석에 앉고, 한 좌석에 한 명만 앉도록 하는 서로 다른 배치의 수를 구하여라.

경우의 수가 매우 클 수 있으므로 \(1\,000\,000\,007\) 로 나눈 나머지를 출력하여라.

• \(1 \le N \le 16\)
• 표의 각 문자는 0 또는 1 이다.

첫 줄에 손님과 좌석의 수 \(N\) 이 주어진다.

이어지는 \(N\) 개의 줄에 각각 길이 \(N\) 인 문자열이 주어진다. \(i\) 번째 줄의 \(j\) 번째 문자가 1 이면 \(i\) 번째 손님이 \(j\) 번째 좌석에 앉을 수 있음을, 0 이면 앉을 수 없음을 뜻한다.

가능한 배치의 수를 \(1\,000\,000\,007\) 로 나눈 나머지를 한 줄에 출력한다.

riseoj 작성

출처 Original