시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 41 9 6 75.000%

문제

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

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

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

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

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

입력

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

출력

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

예제 입력 1

2 3
...
.#.

예제 출력 1

1

힌트

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

W3sicHJvYmxlbV9pZCI6IjI4NTAiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjMzBcdWFkMDBcdWFjZjUgXHVhZTQwXHVjMTIwXHVjNjAxIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMxMjBcdWM2MDFcdWM3NzRcdWIyOTQgXHViM2M0XHVjMmRjXHVjNzU4IFx1YjQ1MCBcdWM5YzBcdWM4MTBcdWM3NDQgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzIxOFx1YjNjNFx1YWQwMFx1Yzc0NCBcdWMxMjRcdWNlNThcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIzYzRcdWMyZGNcdWIyOTQgUiAmdGltZXM7IFNcdWI4NWMgXHViMDk4XHVkMGMwXHViMGJjIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YzViNFx1YjVhNCBcdWNlNzhcdWM3NDAgXHVjMjE4XHViM2M0XHVhZDAwXHVjNzQ0IFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNWM2XHViMjk0IFx1Y2U3OFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjMTIwXHVjNjAxXHVjNzc0XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHVjNzA0XHVjZTc4XHVjNzU4IFx1YmMxNFx1Yjg1YyBcdWM3MDRcdWFjZmMgXHVhYzAwXHVjN2E1IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWM1NDRcdWI3OTggXHVjZTc4XHVjNzU4IFx1YmMxNFx1Yjg1YyBcdWM1NDRcdWI3OThcdWI5N2MgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0IFx1YzIxOFx1YjNjNFx1YWQwMFx1Yzc0NCBcdWMxMjRcdWNlNThcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMyMThcdWIzYzRcdWFkMDBcdWM3NDQgXHViMTkzXHVjNzQ0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNzQwIFx1YmU0OCBcdWMwYzFcdWQwZGNcdWI4NWMgXHViNDUwXHVhYzcwXHViMDk4LCBcdWM1NDRcdWI3OTggNlx1YWMwMFx1YzljMCBcdWQwYzBcdWM3ODUgXHVjOTExIFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWMxMjRcdWNlNThcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9waXBlLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDM0OHB4OyBoZWlnaHQ6IDY4cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzIxOFx1YjNjNFx1YWQwMFx1Yzc0NCBcdWIxOTNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjMTI0XHVjZTU4XHVkNTVjIFx1ZDMwY1x1Yzc3NFx1ZDUwNFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWJiM2NcdWM3NzQgXHVjMGM4XHViYTc0IFx1YzU0OFx1YjQxY1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViM2M0XHVjMmRjXHVjNzU4IFx1ZDA2Y1x1YWUzMCBSXHVhY2ZjIFNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IFIsIFMgJmxlOyAxMCkgXHViMmU0XHVjNzRjIFJcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzIxOFx1YjNjNFx1YWQwMFx1Yzc0NCBcdWIxOTNcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NTggXHVjODE1XHViY2Y0XHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gJiMzOTsuJiMzOTtcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzIxOFx1YjNjNFx1YWQwMFx1Yzc0NCBcdWIxOTNcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjI5NCBcdWFjZjNcdWM3NzRcdWFjZTAsICYjMzk7IyYjMzk7XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWIxOTNcdWM3NDQgXHVjMjE4IFx1YzVjNlx1YjI5NCBcdWFjZjNcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWIzYzRcdWMyZGNcdWM1ZDAgXHVjMjE4XHViM2M0XHVhZDAwXHVjNzQ0IFx1YzEyNFx1Y2U1OFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIDEwMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cclxuXHRcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzQwIFx1ZDU1YyBcdWFjMDBcdWM5YzAgXHViYzI5XHViYzk1XHViOWNjIFx1YWMwMFx1YjJhNVx1ZDU1OFx1YjJlNC48XC9wPlxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BpcGUyLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDE4N3B4OyBoZWlnaHQ6IDEyMHB4O1wiIFwvPjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjg1MCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlZPREEiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvLCB0aGUgbWFkIHBsdW1iZXIsIHdhcyBoaXJlZCB0byBjb25zdHJ1Y3QgYSB3YXRlciBzdXBwbHkgbmV0d29yayBiZXR3ZWVuIHR3byBsb2NhdGlvbnMgaW4gYSBjaXR5LiBUaGUgY2l0eSBtYXAgY2FuIGJlIHJlcHJlc2VudGVkIGFzIGEgUiAmdGltZXM7IFMgZ3JpZC4gU29tZSBjZWxscyBhcmUgbm90IHN1aXRhYmxlIGZvciBwbGFjaW5nIHdhdGVyIHBpcGVzLiBMb2NhdGlvbnMgTWlya28gbmVlZHMgdG8gY29ubmVjdCBhcmUgcGxhY2VkIGRpcmVjdGx5IGFib3ZlIHRoZSB0b3AgbGVmdCBjZWxsIG9mIHRoZSBncmlkLCBhbmQgZGlyZWN0bHkgYmVsb3cgdGhlIGJvdHRvbSByaWdodCBjZWxsLjxcL3A+XHJcblxyXG48cD5FYWNoIHN1aXRhYmxlIGNlbGwgTWlya28gY2FuIGVpdGhlciBsZWF2ZSBlbXB0eSBvciB1c2UgaXQgZm9yIHBsYWNpbmcgb25lIG9mIHRoZSBmb2xsb3dpbmcgNiBwaXBlIHR5cGVzOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3BpcGUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NjhweDsgd2lkdGg6MzQ4cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+RmluZCB0aGUgbnVtYmVyIG9mIHdheXMgdGhhdCBwaXBlcyBjYW4gYmUgcGxhY2VkIHRvIGNvbm5lY3QgdGhlIHR3byBsb2NhdGlvbnMgd2l0aCBhIGNvbnRpbnVvdXMgcGlwZSAod2F0ZXIgbXVzdCBub3QgYmUgc3BpbGxlZCkuIEFsbCBwbGFjZWQgcGlwZSBwYXJ0cyBtdXN0IGJlIGluIHVzZS48XC9wPlxyXG5cclxuPHA+T3V0cHV0IHRoZSBzb2x1dGlvbiBtb2R1bG8gMTAwMDcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlcnMgUiBhbmQgUyAoMiAmbGU7IFIsIFMgJmxlOyAxMCksIHRoZSBudW1iZXIgb2Ygcm93cyBhbmQgY29sdW1ucyBvZiB0aGUgY2l0eSBncmlkLCByZXNwZWN0aXZlbHkuIEVhY2ggb2YgdGhlIG5leHQgUiBsaW5lcyBjb250YWlucyBleGFjdGx5IFMgY2hhcmFjdGVyczogJmxzcXVvOy4mcnNxdW87IGlmIHRoZSBjZWxsIGlzIHN1aXRhYmxlIGZvciBwbGFjaW5nIHBpcGVzLCBhbmQgJmxzcXVvOyMmcnNxdW87IGlmIG5vdC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZXF1aXJlZCBudW1iZXIgb2Ygd2F5cyBtb2R1bG8gMTAwMDcuPFwvcD5cclxuIiwiaGludCI6IjxwPlRoaXMgaXMgdGhlIG9ubHkgcG9zc2libGUgc29sdXRpb246PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcGlwZTIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MTIwcHg7IHdpZHRoOjE4N3B4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=