시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 45 12 8 72.727%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

2 3
...
.#.

예제 출력 1

1

힌트

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

W3sicHJvYmxlbV9pZCI6IjI4NTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMzBcdWFkMDBcdWFjZjUgXHVhZTQwXHVjMTIwXHVjNjAxIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViM2M0XHVjMmRjXHVjNzU4IFx1YjQ1MCBcdWM5YzBcdWM4MTBcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzIxOFx1YjNjNFx1YWQwMFx1Yzc0NCBcdWMxMjRcdWNlNThcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIzYzRcdWMyZGNcdWIyOTQgUiAmdGltZXM7IFNcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWNlNzhcdWM3NDAgXHVjMjE4XHViM2M0XHVhZDAwXHVjNzQ0IFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNWM2XHViMjk0IFx1Y2U3OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjNzA0XHVjZTc4XHVjNzU4IFx1YmMxNFx1Yjg1YyBcdWM3MDRcdWFjZmMgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OTggXHVjZTc4XHVjNzU4IFx1YmMxNFx1Yjg1YyBcdWM1NDRcdWI3OThcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzIxOFx1YjNjNFx1YWQwMFx1Yzc0NCBcdWMxMjRcdWNlNThcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMyMThcdWIzYzRcdWFkMDBcdWM3NDQgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzQwIFx1YmU0OCBcdWMwYzFcdWQwZGNcdWI4NWMgXHViNDUwXHVhYzcwXHViMDk4LCBcdWM1NDRcdWI3OTggNlx1YWMwMFx1YzljMCBcdWQwYzBcdWM3ODUgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWMxMjRcdWNlNThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9waXBlLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDM0OHB4OyBoZWlnaHQ6IDY4cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzIxOFx1YjNjNFx1YWQwMFx1Yzc0NCBcdWIxOTNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjMTI0XHVjZTU4XHVkNTVjIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWJiM2NcdWM3NzQgXHVjMGM4XHViYTc0IFx1YzU0OCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjNjNFx1YzJkY1x1Yzc1OCBcdWQwNmNcdWFlMzAgUlx1YWNmYyBTXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBSLCBTICZsZTsgMTApIFx1YjJlNFx1Yzc0YyBSXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMyMThcdWIzYzRcdWFkMDBcdWM3NDQgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzU4IFx1YzgxNVx1YmNmNFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICYjMzk7LiYjMzk7XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWMyMThcdWIzYzRcdWFkMDBcdWM3NDQgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVhY2YzXHVjNzc0XHVhY2UwLCAmIzM5OyMmIzM5O1x1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM1YzZcdWIyOTQgXHVhY2YzXHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViM2M0XHVjMmRjXHVjNWQwIFx1YzIxOFx1YjNjNFx1YWQwMFx1Yzc0NCBcdWMxMjRcdWNlNThcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyAxMDAwN1x1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+XHJcblx0XHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWQ1NWMgXHVhYzAwXHVjOWMwIFx1YmMyOVx1YmM5NVx1YjljYyBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9waXBlMi5wbmdcIiBzdHlsZT1cIndpZHRoOiAxODdweDsgaGVpZ2h0OiAxMjBweDtcIiBcLz48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4NTAiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJWT0RBIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbywgdGhlIG1hZCBwbHVtYmVyLCB3YXMgaGlyZWQgdG8gY29uc3RydWN0IGEgd2F0ZXIgc3VwcGx5IG5ldHdvcmsgYmV0d2VlbiB0d28gbG9jYXRpb25zIGluIGEgY2l0eS4gVGhlIGNpdHkgbWFwIGNhbiBiZSByZXByZXNlbnRlZCBhcyBhIFIgJnRpbWVzOyBTIGdyaWQuIFNvbWUgY2VsbHMgYXJlIG5vdCBzdWl0YWJsZSBmb3IgcGxhY2luZyB3YXRlciBwaXBlcy4gTG9jYXRpb25zIE1pcmtvIG5lZWRzIHRvIGNvbm5lY3QgYXJlIHBsYWNlZCBkaXJlY3RseSBhYm92ZSB0aGUgdG9wIGxlZnQgY2VsbCBvZiB0aGUgZ3JpZCwgYW5kIGRpcmVjdGx5IGJlbG93IHRoZSBib3R0b20gcmlnaHQgY2VsbC48XC9wPlxyXG5cclxuPHA+RWFjaCBzdWl0YWJsZSBjZWxsIE1pcmtvIGNhbiBlaXRoZXIgbGVhdmUgZW1wdHkgb3IgdXNlIGl0IGZvciBwbGFjaW5nIG9uZSBvZiB0aGUgZm9sbG93aW5nIDYgcGlwZSB0eXBlczombmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9waXBlLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjY4cHg7IHdpZHRoOjM0OHB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpbmQgdGhlIG51bWJlciBvZiB3YXlzIHRoYXQgcGlwZXMgY2FuIGJlIHBsYWNlZCB0byBjb25uZWN0IHRoZSB0d28gbG9jYXRpb25zIHdpdGggYSBjb250aW51b3VzIHBpcGUgKHdhdGVyIG11c3Qgbm90IGJlIHNwaWxsZWQpLiBBbGwgcGxhY2VkIHBpcGUgcGFydHMgbXVzdCBiZSBpbiB1c2UuPFwvcD5cclxuXHJcbjxwPk91dHB1dCB0aGUgc29sdXRpb24gbW9kdWxvIDEwMDA3LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXJzIFIgYW5kIFMgKDIgJmxlOyBSLCBTICZsZTsgMTApLCB0aGUgbnVtYmVyIG9mIHJvd3MgYW5kIGNvbHVtbnMgb2YgdGhlIGNpdHkgZ3JpZCwgcmVzcGVjdGl2ZWx5LiBFYWNoIG9mIHRoZSBuZXh0IFIgbGluZXMgY29udGFpbnMgZXhhY3RseSBTIGNoYXJhY3RlcnM6ICZsc3F1bzsuJnJzcXVvOyBpZiB0aGUgY2VsbCBpcyBzdWl0YWJsZSBmb3IgcGxhY2luZyBwaXBlcywgYW5kICZsc3F1bzsjJnJzcXVvOyBpZiBub3QuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IG11c3QgY29udGFpbiB0aGUgcmVxdWlyZWQgbnVtYmVyIG9mIHdheXMgbW9kdWxvIDEwMDA3LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5UaGlzIGlzIHRoZSBvbmx5IHBvc3NpYmxlIHNvbHV0aW9uOjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BpcGUyLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjEyMHB4OyB3aWR0aDoxODdweFwiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d