시간 제한메모리 제한제출정답맞은 사람정답 비율
4 초 512 MB8244100.000%

문제

현욱은 학교 미술 과제로 여러 장의 색종이를 붙여 만든 작품을 내려고 한다. 현욱은 우선 색종이를 붙일 수 있는 위아래로 $N$칸, 좌우로 $M$칸 크기($ 1 \le N, M \le 2000 $)인 직사각형 모양의 모눈 종이를 준비했다.

현욱은 이 모눈 종이의 일부 칸에 색칠을 하고, 나머지 칸들은 색종이를 붙여서 채우려고 한다. 현욱은 가로, 세로 크기가 모눈 크기의 배수가 되는 여러 가지 종류의 색종이를 가지고 있다. 이 중에서 한 종류의 색종이를 골라 그 색종이만을 이용해서 모든 칸을 채우려고 하는데, 다음 조건을 만족하면서 색종이를 붙이려고 한다.

  • 색종이는 모눈 칸에 정확히 맞춰서 붙여야 하며, 회전할 수 없다.
  • 색종이끼리는 서로 겹쳐 붙여도 되지만, 기존에 색을 칠해둔 칸과 겹쳐 붙여서는 안 된다.
  • 색칠되지 않은 모든 칸은 한 장 이상의 색종이가 덮어야만 한다.

현욱은 이런 조건을 만족하는 색종이의 종류가 얼마나 다양한지 궁금해졌다. 현욱을 도와 주어진 조건을 만족하는 색종이 크기의 경우의 수를 계산해보자.

입력

첫 줄에 종이의 크기 $N$, $M$ 이 공백으로 구분되어 주어진다($ 1 \le N, M \le 2000 $).

둘째줄부터 $N$줄에 걸쳐 모눈 종이의 현재 상태가 주어진다. '.'의 경우 색이 칠해지지 않은 칸, '#'의 경우 색이 칠해진 칸이다. 색이 칠해지지 않은 칸은 반드시 하나 이상 존재한다.

출력

첫째 줄에 문제에서 제시된 조건을 만족하는 색종이의 크기가 몇 종류인지 출력한다.

서브태스크 1 (40점)

$ 1 \le N, M \le 15 $

서브태스크 2 (16점)

$ 1 \le N, M \le 100 $

서브태스크 3 (14점)

$ 1 \le N, M \le 400 $

서브태스크 4 (55점)

추가 제한 없음

예제 입력 1

3 3
..#
...
#..

예제 출력 1

4

1x1, 1x2, 2x1, 2x2 의 4종류의 색종이가 조건을 만족한다. 색종이를 회전할 수 없기 때문에 1x2 크기와 2x1 크기는 서로 다른 종류로 생각한다.

예제 입력 2

8 9
.........
.........
.........
...#.....
.....#...
....#....
.........
.........

예제 출력 2

4

예제 입력 3

9 9
######...
######...
######...
#........
#.....###
#.....###
#####....
#####....
#####....

예제 출력 3

9

예제 입력 4

5 5
.....
....#
...##
..###
.####

예제 출력 4

1

출처

Contest > 소프트콘 > 제3회 소프트콘 G번

채점 및 기타 정보

  • 예제는 채점하지 않는다.