코드 자물쇠

시간 제한1초메모리 제한1024 MB

요약

각각 M개 칸으로 이루어진 N개 원판을 회전시켜, 어떤 열의 모든 칸이 구멍이 되는 경우의 수를 센다.

난이도: 보통10점 중 6점
유형: 비트 연산, 조합론, 완전 탐색, 수학
정답자: 아직 제출이 없습니다

문제

Åskold는 방금 새 코드 자물쇠를 샀다. 판매원은 이 자물쇠가 매우 안전하다고 장담했지만, Åskold는 믿지 않는다. 그래서 그는 자물쇠를 여는 서로 다른 조합의 수를 계산해 달라고 부탁한다.

코드 자물쇠는 $N$ 개의 인접한 원판으로 이루어져 있다. 각 원판에는 $M$ 개의 칸이 있고, 각 칸은 채워져 있거나 구멍이다. 코드를 입력하려면 원판을 돌려야 한다. 각 원판은 $M$ 가지 위치로 설정할 수 있는데, 이는 기계 구조상 원판을 한 칸보다 작게 돌릴 수 없기 때문이다. 자물쇠는 어딘가에서 구멍이 모든 원판을 같은 위치에서 통과하면 열린다.

각 원판은 "."과 "#"으로 이루어진 문자열로 나타낼 수 있으며, "."은 구멍이 뚫린 칸을, "#"은 채워진 칸을 나타낸다. 원판을 한 칸 회전하는 것은 문자열의 마지막 문자를 맨 앞으로 옮기는 것으로 볼 수 있다. 원판을 $M$ 칸 회전하면 처음 위치로 돌아온다.

예를 들어 원판 ".#..#"은 다음 5가지 위치로 설정할 수 있다.


`.#..#`	`#.#..`	`.#.#.`	`..#.#`	`#..#.`

따라서 $N$ 개의 원판을 설정하는 방법은 총 $M^N$ 가지이고, 모든 원판의 문자열을 위아래로 놓았을 때 어떤 열이 전부 "."으로만 이루어져 있으면 자물쇠가 열린다. 자물쇠가 열리도록 원판을 설정하는 방법의 수를 계산하는 프로그램을 작성하시오.

입력

프로그램은 먼저 두 정수를 읽는다. $N$ ( $1\le N \le 12$ )은 원판의 수이고, $M$ ( $1\le M \le 12$ )은 칸의 수이다.

그다음 프로그램은 $N$ 개의 원판에 대한 설명을 읽는다. 각 원판은 "."과 "#"으로 이루어진 $M$ 글자 한 줄로 주어진다.

출력

프로그램은 자물쇠가 열리도록 원판을 설정하는 방법의 수를 나타내는 정수 하나를 출력한다.

예제4

예제 1
입력
```
2 3
.#.
#..
```
예상 출력
```
9
```
예제 2
입력
```
3 4
..#.
####
..#.
```
예상 출력
```
0
```
예제 3
입력
```
3 2
#.
.#
#.
```
예상 출력
```
2
```
예제 4
입력
```
2 3
..#
.##
```
예상 출력
```
6
```