시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 31 6 3 60.000%

문제

선영이는 도시의 두 지점을 연결하는 수도관을 설치하려고 한다.

도시는 R × S로 나타낼 수 있다. 어떤 칸은 수도관을 놓을 수 없는 칸이다.

선영이는 가장 왼쪽 위칸의 바로 위과 가장 오른쪽 아래 칸의 바로 아래를 연결하는 수도관을 설치하려고 한다.

수도관을 놓을 수 있는 칸은 빈 상태로 두거나, 아래 6가지 타입 중 하나를 설치할 수 있다.

수도관을 놓는 방법의 수를 구하는 프로그램을 작성하시오. 설치한 파이프는 모두 사용해야 한다. 또, 물이 새면 안된다.

입력

첫째 줄에 도시의 크기 R과 S가 주어진다. (2 ≤ R, S ≤ 10) 다음 R개 줄에는 수도관을 놓을 수 있는 칸의 정보가 주어진다. '.'인 경우에는 수도관을 놓을 수 있는 곳이고, '#'인 경우에는 놓을 수 없는 곳이다.

출력

첫째 줄에 도시에 수도관을 설치하는 방법의 수를 10007로 나눈 나머지를 출력한다.

예제 입력

2 3
...
.#.

예제 출력

1

힌트

아래와 같은 한 가지 방법만 가능하다.