수도관 설치 방법 세기

도시는 R x S 크기의 격자로 나타낸다. 각 칸은 수도관을 놓을 수 있는 칸이거나, 놓을 수 없는 칸이다.

가장 왼쪽 위 칸의 위쪽 바깥 지점에서 시작해 가장 오른쪽 아래 칸의 아래쪽 바깥 지점까지 물이 흐르도록 수도관을 설치하려고 한다.

수도관을 놓을 수 있는 칸은 비워 둘 수 있고, 다음 6가지 종류 중 하나의 파이프를 설치할 수 있다.

설치한 파이프는 모두 실제 물길에 포함되어야 하며, 어떤 연결부에서도 물이 새면 안 된다. 가능한 설치 방법의 수를 구하시오.

첫째 줄에 도시의 크기 R과 S가 주어진다. (2 <= R, S <= 10)

이어지는 R개의 줄에는 각 칸의 정보가 주어진다. '.'은 수도관을 놓을 수 있는 칸이고, '#'은 수도관을 놓을 수 없는 칸이다.

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