다이얼 자물쇠

Åskold는 방금 새 다이얼 자물쇠를 샀다. 판매자는 이 자물쇠가 매우 안전하다고 장담했지만, Åskold는 확신하지 못한다. 그래서 자물쇠를 여는 서로 다른 조합의 수를 계산해 주기를 원한다.

이 자물쇠는 서로 맞닿아 있는 원판 $N$개로 이루어진다. 각 원판에는 $M$개의 구획이 있으며, 각 구획은 채워져 있거나 구멍이다. 암호를 입력하려면 원판을 돌린다. 장치의 구조상 원판을 한 구획보다 적게 돌릴 수 없으므로, 각 원판은 서로 다른 $M$개의 위치로 설정할 수 있다. 모든 원판의 같은 위치를 관통하는 구멍이 적어도 하나 있으면 자물쇠가 열린다.

각 원판은 ”.”와 ”#”로 이루어진 문자열로 나타낼 수 있으며, 여기서 ”.”는 구멍이 있는 구획을, ”#”는 채워진 구획을 나타낸다. 원판을 한 단계 돌리는 것은 문자열의 마지막 문자를 가져와 맨 앞에 놓는 것으로 볼 수 있다. 원판을 $M$단계 돌리면 시작했던 위치로 돌아온다.

예를 들어, 원판 ”.#..#”는 다음 5개의 위치로 설정할 수 있다.

`.#..#`  |
`#.#..`  |
`.#.#.`  |
`..#.#`  |
`#..#.`

원판 $N$개를 설정하는 방법은 모두 $M^N$가지이며, 모든 원판의 문자열을 위아래로 겹쳐 출력했을 때 어느 열이든 ”.”만으로 이루어져 있으면 자물쇠가 열린다. 자물쇠가 열리도록 원판을 설정하는 서로 다른 방법의 수를 계산하는 프로그램을 작성한다.

배점

여러 테스트 케이스 그룹으로 제출한 해답을 평가한다. 한 그룹의 점수를 받으려면 그 그룹의 모든 테스트 케이스를 통과해야 한다.

그룹 | 배점 | 제한

$1$ |$40$| $M, N \le 5$

$2$ |$20$| $N \le 8, M \le 10$, 그리고 각 원판에는 구멍이 최대 3개 있다.

$3$ |$40$| 추가 제한 없음.

첫째 줄에 원판의 수와 구획의 수를 나타내는 정수 $N, M$ ($1 \leq N, M \leq 12$)가 주어진다.

이후 각각 원판 하나를 설명하는 $N$개의 줄이 주어진다. 각 원판은 ”.”와 ”#”로 이루어진 $M$개의 문자로 설명된다.

자물쇠가 열리도록 원판을 설정하는 방법의 수를 정수로 출력한다.

• 첫 번째 예제에서는 가능한 아홉 가지 설정 모두 자물쇠를 연다.

• 두 번째 예제에서는 두 번째 원판에 구멍이 하나도 없으므로 어떤 설정도 자물쇠를 열지 못한다.

• 세 번째 예제에서는 다음 두 가지 설정이 자물쇠를 연다.

  .# | #.

  .# | #.

  .# | #.

• 네 번째 예제에서는 자물쇠를 열지 못하는 설정이 가능한 아홉 가지 중 세 가지 있다. 두 번째 원판의 ”.”가 첫 번째 원판의 ”#” 바로 아래에 있는 경우이다.