신성한 허수아비

시간 제한2초메모리 제한512 MB

요약

R x C 격자의 빈 칸 부분집합 가운데 각 행에 허수아비가 하나 이상 있고 이웃한 두 열마다 허수아비가 하나 이상 있는 경우의 수를 1e9+7로 나눈 나머지로 구한다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 비트 연산, 조합론, 행렬
정답자: 아직 제출이 없습니다

문제

Nerissa는 $R \times C$ 크기의 직사각형 논을 가지고 있다. 논은 크기가 같은 작은 정사각형 칸 $R$ 행 $C$ 열로 나뉜다. 각 칸은 빈 흙(어떤 용도로도 쓸 수 있는 빈 칸) 또는 벼가 심긴 흙이다.

새나 참새 같은 새가 작물을 해치지 못하도록 Nerissa는 논에 허수아비를 세우기로 했다. 허수아비는 빈 칸에만 놓을 수 있다. 또한 다른 사람이 작물을 훔치지 못하도록 허수아비 배치는 신성해야 한다. 배치가 신성하다는 것은 다음 조건을 모두 만족한다는 뜻이다:

각 행에 허수아비가 최소 하나 있다.
연속한 두 열마다 허수아비가 최소 하나 있다.

신성한 배치는 서로 몇 가지인가? 한 배치에만 허수아비가 있는 칸이 있으면 두 배치는 서로 다르다. 이 개수를 구하라.

입력

첫째 줄에 논 크기를 나타내는 두 정수 $R$ $C$ ( $1 \le R \le 14$ , $1 \le C \le 1000$ )가 주어진다. 다음 $R$ 줄에 논 상태가 주어진다. 각 줄은 길이가 $C$ 인 문자열이다. 각 칸은 빈 흙을 뜻하는 . 또는 벼가 심긴 흙을 뜻하는 v로 표시된다.

출력

서로 다른 신성한 배치의 개수를 한 줄에 출력한다. 출력이 매우 클 수 있으므로 $1,000,000,007$ 로 나눈 나머지를 출력한다.

힌트

두 번째 샘플에서는 가능한 배치가 5가지이다. 한 행에 놓을 수 있는 위치가 세 칸이므로 비어 있지 않은 부분집합 중에서 양쪽 이웃 열 쌍을 모두 덮는 경우가 5가지가 된다.

세 번째 샘플에서는 첫 행에 허수아비를 놓을 칸이 없다. 각 행에 최소 하나가 있어야 하므로 가능한 배치가 없다.

다섯 번째 샘플에서도 가능한 배치가 5가지이다. 두 행의 빈 칸 위치가 서로 어긋나 있어 행 조건과 열 쌍 조건을 함께 만족하는 경우가 5가지로 제한된다.

예제5

예제 1
입력
```
2 2
v.
..
```
예상 출력
```
3
```
예제 2
입력
```
1 3
...
```
예상 출력
```
5
```
예제 3
입력
```
2 3
vvv
...
```
예상 출력
```
0
```
예제 4
입력
```
3 3
...
.v.
...
```
예상 출력
```
145
```
예제 5
입력
```
2 4
.vv.
.v.v
```
예상 출력
```
5
```