동굴 그림

Bessie는 화가가 되어 동굴 그림을 그리고 있다! 현재 작업 중인 그림은 높이가 $N$인 격자로, 각 행에는 정확히 $M$개의 칸이 있다 ($1\le N,M\le 1000$). 각 칸은 비어 있거나, 암석으로 채워져 있거나, 물로 채워져 있다. Bessie는 이미 암석이 들어 있는 칸을 모두 칠했으며, 그림의 가장자리 전체도 포함된다. 이제 Bessie는 그림이 실제라면 물의 알짜 이동이 없도록 몇몇 빈 칸을 물로 채우려고 한다. 위에서 $i$번째 행에 있는 칸의 높이를 $N+1-i$로 정의하자. Bessie는 그림이 다음 조건을 만족하기를 원한다:

칸 $a$가 물로 채워져 있다고 하자. 그러면 $a$보다 높지 않은 빈 칸 또는 물 칸만을 사용하여 $a$에서 칸 $b$로 가는 경로가 존재하고, 경로 위의 인접한 두 칸이 모두 변을 공유한다면, $b$도 물로 채워져 있어야 한다.

Bessie가 만들 수 있는 서로 다른 그림의 수를 $10^9+7$로 나눈 나머지를 구하라. Bessie는 빈 칸을 원하는 만큼 물로 채울 수 있으며, 하나도 채우지 않거나 전부 채울 수도 있다.

첫째 줄에는 공백으로 구분된 두 정수 $N$과 $M$이 주어진다.

다음 $N$개의 줄에는 각각 $M$개의 문자가 주어진다. 각 문자는 '.' 또는 '#'이며, 각각 빈 칸과 암석으로 채워진 칸을 나타낸다. 첫째 행과 마지막 행, 첫째 열과 마지막 열에는 '#'만 들어 있다.

조건을 만족하는 그림의 수를 $10^9+7$로 나눈 나머지를 하나의 정수로 출력한다.

둘째 행의 어떤 칸이 물로 채워져 있다면, 모든 빈 칸이 물로 채워져야 한다. 그렇지 않다면 그러한 칸은 물로 채워지지 않는다고 가정하자. 그러면 Bessie는 셋째 행에 있는 가로로 연속된 세 개의 빈 칸 영역 각각을 물로 채울지 선택할 수 있다. 따라서 그림의 수는 $1+2^3=9$이다.