수도관 설치 방법 세기
시간 제한2초메모리 제한128 MB
6가지 파이프 모양으로 좌상단 입구에서 우하단 출구까지 이어지는 하나의 경로를 막힌 칸이 있는 격자에서 설치하는 방법의 수를 10007로 나눈 나머지로 구합니다.
문제
도시는 R x S 크기의 격자로 나타낸다. 각 칸은 수도관을 놓을 수 있는 칸이거나, 놓을 수 없는 칸이다.
가장 왼쪽 위 칸의 위쪽 바깥 지점에서 시작해 가장 오른쪽 아래 칸의 아래쪽 바깥 지점까지 물이 흐르도록 수도관을 설치하려고 한다.
수도관을 놓을 수 있는 칸은 비워 둘 수 있고, 다음 6가지 종류 중 하나의 파이프를 설치할 수 있다.
설치한 파이프는 모두 실제 물길에 포함되어야 하며, 어떤 연결부에서도 물이 새면 안 된다. 가능한 설치 방법의 수를 구하시오.
입력
첫째 줄에 도시의 크기 R과 S가 주어진다. (2 <= R, S <= 10)
이어지는 R개의 줄에는 각 칸의 정보가 주어진다. '.'은 수도관을 놓을 수 있는 칸이고, '#'은 수도관을 놓을 수 없는 칸이다.
출력
수도관을 설치하는 방법의 수를 10007로 나눈 나머지를 출력한다.