시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 130 36 20 52.632%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

2 3
...
.#.

예제 출력 1

1

힌트

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

W3sicHJvYmxlbV9pZCI6IjI4NTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMzBcdWFkMDBcdWFjZjUgXHVhZTQwXHVjMTIwXHVjNjAxIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViM2M0XHVjMmRjXHVjNzU4IFx1YjQ1MCBcdWM5YzBcdWM4MTBcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzIxOFx1YjNjNFx1YWQwMFx1Yzc0NCBcdWMxMjRcdWNlNThcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIzYzRcdWMyZGNcdWIyOTQgUiAmdGltZXM7IFNcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWNlNzhcdWM3NDAgXHVjMjE4XHViM2M0XHVhZDAwXHVjNzQ0IFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNWM2XHViMjk0IFx1Y2U3OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjNzA0XHVjZTc4XHVjNzU4IFx1YmMxNFx1Yjg1YyBcdWM3MDRcdWFjZmMgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OTggXHVjZTc4XHVjNzU4IFx1YmMxNFx1Yjg1YyBcdWM1NDRcdWI3OThcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzIxOFx1YjNjNFx1YWQwMFx1Yzc0NCBcdWMxMjRcdWNlNThcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMyMThcdWIzYzRcdWFkMDBcdWM3NDQgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzQwIFx1YmU0OCBcdWMwYzFcdWQwZGNcdWI4NWMgXHViNDUwXHVhYzcwXHViMDk4LCBcdWM1NDRcdWI3OTggNlx1YWMwMFx1YzljMCBcdWQwYzBcdWM3ODUgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWMxMjRcdWNlNThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9waXBlLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDM0OHB4OyBoZWlnaHQ6IDY4cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzIxOFx1YjNjNFx1YWQwMFx1Yzc0NCBcdWIxOTNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjMTI0XHVjZTU4XHVkNTVjIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWJiM2NcdWM3NzQgXHVjMGM4XHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWQwNmNcdWFlMzAgUlx1YWNmYyBTXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBSLCBTICZsZTsgMTApIFx1YjJlNFx1Yzc0YyBSXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMThcdWIzYzRcdWFkMDBcdWM3NDQgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICYjMzk7LiYjMzk7XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWMyMThcdWIzYzRcdWFkMDBcdWM3NDQgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVjNzc0XHVhY2UwLCAmIzM5OyMmIzM5O1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVhY2YzXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViM2M0XHVjMmRjXHVjNWQwIFx1YzIxOFx1YjNjNFx1YWQwMFx1Yzc0NCBcdWMxMjRcdWNlNThcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyAxMDAwN1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWQ1NWMgXHVhYzAwXHVjOWMwIFx1YmMyOVx1YmM5NVx1YjljYyBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGlwZTIucG5nXCIgc3R5bGU9XCJ3aWR0aDogMTg3cHg7IGhlaWdodDogMTIwcHg7XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODUwIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVk9EQSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28sIHRoZSBtYWQgcGx1bWJlciwgd2FzIGhpcmVkIHRvIGNvbnN0cnVjdCBhIHdhdGVyIHN1cHBseSBuZXR3b3JrIGJldHdlZW4gdHdvIGxvY2F0aW9ucyBpbiBhIGNpdHkuIFRoZSBjaXR5IG1hcCBjYW4gYmUgcmVwcmVzZW50ZWQgYXMgYSBSICZ0aW1lczsgUyBncmlkLiBTb21lIGNlbGxzIGFyZSBub3Qgc3VpdGFibGUgZm9yIHBsYWNpbmcgd2F0ZXIgcGlwZXMuIExvY2F0aW9ucyBNaXJrbyBuZWVkcyB0byBjb25uZWN0IGFyZSBwbGFjZWQgZGlyZWN0bHkgYWJvdmUgdGhlIHRvcCBsZWZ0IGNlbGwgb2YgdGhlIGdyaWQsIGFuZCBkaXJlY3RseSBiZWxvdyB0aGUgYm90dG9tIHJpZ2h0IGNlbGwuPFwvcD5cclxuXHJcbjxwPkVhY2ggc3VpdGFibGUgY2VsbCBNaXJrbyBjYW4gZWl0aGVyIGxlYXZlIGVtcHR5IG9yIHVzZSBpdCBmb3IgcGxhY2luZyBvbmUgb2YgdGhlIGZvbGxvd2luZyA2IHBpcGUgdHlwZXM6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGlwZS5wbmdcIiBzdHlsZT1cImhlaWdodDo2OHB4OyB3aWR0aDozNDhweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaW5kIHRoZSBudW1iZXIgb2Ygd2F5cyB0aGF0IHBpcGVzIGNhbiBiZSBwbGFjZWQgdG8gY29ubmVjdCB0aGUgdHdvIGxvY2F0aW9ucyB3aXRoIGEgY29udGludW91cyBwaXBlICh3YXRlciBtdXN0IG5vdCBiZSBzcGlsbGVkKS4gQWxsIHBsYWNlZCBwaXBlIHBhcnRzIG11c3QgYmUgaW4gdXNlLjxcL3A+XHJcblxyXG48cD5PdXRwdXQgdGhlIHNvbHV0aW9uIG1vZHVsbyAxMDAwNy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VycyBSIGFuZCBTICgyICZsZTsgUiwgUyAmbGU7IDEwKSwgdGhlIG51bWJlciBvZiByb3dzIGFuZCBjb2x1bW5zIG9mIHRoZSBjaXR5IGdyaWQsIHJlc3BlY3RpdmVseS4gRWFjaCBvZiB0aGUgbmV4dCBSIGxpbmVzIGNvbnRhaW5zIGV4YWN0bHkgUyBjaGFyYWN0ZXJzOiAmbHNxdW87LiZyc3F1bzsgaWYgdGhlIGNlbGwgaXMgc3VpdGFibGUgZm9yIHBsYWNpbmcgcGlwZXMsIGFuZCAmbHNxdW87IyZyc3F1bzsgaWYgbm90LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlcXVpcmVkIG51bWJlciBvZiB3YXlzIG1vZHVsbyAxMDAwNy48XC9wPlxyXG4iLCJoaW50IjoiPHA+VGhpcyBpcyB0aGUgb25seSBwb3NzaWJsZSBzb2x1dGlvbjo8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9waXBlMi5wbmdcIiBzdHlsZT1cImhlaWdodDoxMjBweDsgd2lkdGg6MTg3cHhcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==