시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 (추가 시간 없음) 256 MB131538828836.090%

문제

어느 날, 네오는 길을 걷다가 격자판 하나를 주웠다. 그 격자판은 N M 열로, 각 격자는 흰색 또는 검은색으로 칠해져 있다.

네오는 이 격자판에는 분명 엄청난 비밀이 숨겨져 있을 것이라고 생각해 나중에 해독을 시도해 보기로 하였다. 아래 그림은 격자판 상태의 예시이다.

네오가 잠시 외출한 사이, 프로도는 네오의 격자판을 이리저리 살펴보았다. 얼마 뒤, 하나의 격자를 누르게 되면 자신을 포함해 그 격자와 연결된 모든 칸들의 색이 반전된다는 사실을 관찰할 수 있었다. 여기서, 두 격자가 연결되었다는 것은 두 격자 사이를 서로 같은 색이면서 변을 공유하는 격자들로만 이동하여 오갈 수 있다는 것을 뜻한다. 집으로 돌아온 네오는 프로도가 격자판의 상태를 바꿔버렸다는 것을 알고 좌절했다. 하지만 최종 상태를 알고 있기 때문에, 초기 상태를 추측할 수 있을 것이라는 희망을 가지기로 했다.

프로도는 격자판을 0번 이상 눌렀다(아직 한 번도 누르지 않은 상태일 수도 있다). 현재 각 격자의 색깔이 주어졌을 때, 격자판의 초기 상태로 가능한 경우의 수를 1,000,000,007(109 + 7)로 나눈 나머지를 구하여라. 두 격자판의 상태가 다르다는 것은, 같은 위치의 격자의 색이 다른 경우가 존재할 때로 정의한다.

입력

첫 줄에 격자판의 행의 수 N 과 열의 수 M 이 주어진다. (1 ≤ N, M ≤ 2,000)

둘째 줄부터 N 개의 줄에 걸쳐 현재 각 격자의 색을 나타내는 문자열이 주어진다.

N 개의 줄 중에서 i 번째 줄의 j 번째 문자는 i j 열 격자의 색을 나타내며, 'B'인 경우 검은색, 'W'인 경우 흰색임을 나타낸다.

출력

첫 줄에 격자의 초기 상태로 가능한 경우의 수를 1,000,000,007(109 + 7)로 나눈 나머지를 출력한다.

예제 입력 1

2 2
WB
BB

예제 출력 1

2
WB
BB

WB
BW

이렇게 두 가지가 가능하다.

W3sicHJvYmxlbV9pZCI6IjE1OTk5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHViNGE0XHVjOWQxXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM1YjRcdWIyOTAgXHViMGEwLCBcdWIxMjRcdWM2MjRcdWIyOTQgXHVhZTM4XHVjNzQ0IFx1YWM3N1x1YjJlNFx1YWMwMCBcdWFjYTlcdWM3OTBcdWQzMTAgXHVkNTU4XHViMDk4XHViOTdjIFx1YzhmY1x1YzZlMFx1YjJlNC4gXHVhZGY4IFx1YWNhOVx1Yzc5MFx1ZDMxMFx1Yzc0MCA8ZW0+TiA8XC9lbT5cdWQ1ODkgPGVtPk0gPFwvZW0+XHVjNWY0XHViODVjLCBcdWFjMDEgXHVhY2E5XHVjNzkwXHViMjk0IFx1ZDc3MFx1YzBjOSBcdWI2MTBcdWIyOTQgXHVhYzgwXHVjNzQwXHVjMGM5XHVjNzNjXHViODVjIFx1Y2U2MFx1ZDU3NFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjEyNFx1YzYyNFx1YjI5NCBcdWM3NzQgXHVhY2E5XHVjNzkwXHVkMzEwXHVjNWQwXHViMjk0IFx1YmQ4NFx1YmE4NSBcdWM1YzRcdWNjYWRcdWIwOWMgXHViZTQ0XHViYzAwXHVjNzc0IFx1YzIyOFx1YWNhOFx1YzgzOCBcdWM3ODhcdWM3NDQgXHVhYzgzXHVjNzc0XHViNzdjXHVhY2UwIFx1YzBkZFx1YWMwMVx1ZDU3NCBcdWIwOThcdWM5MTFcdWM1ZDAgXHVkNTc0XHViM2M1XHVjNzQ0IFx1YzJkY1x1YjNjNFx1ZDU3NCBcdWJjZjRcdWFlMzBcdWI4NWMgXHVkNTU4XHVjNjAwXHViMmU0LiBcdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIFx1YWNhOVx1Yzc5MFx1ZDMxMCBcdWMwYzFcdWQwZGNcdWM3NTggXHVjNjA4XHVjMmRjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2NmZWQwYjc0LTQwNjEtNGNhZi05N2EyLWQzY2UwMGVkM2VkZlwvLVwvY3JvcFwvODA4eDM4M1wvMTYxLDYwXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA4MDhweDsgaGVpZ2h0OiAzODNweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViMTI0XHVjNjI0XHVhYzAwIFx1YzdhMFx1YzJkYyBcdWM2NzhcdWNkOWNcdWQ1NWMgXHVjMGFjXHVjNzc0LCBcdWQ1MDRcdWI4NWNcdWIzYzRcdWIyOTQgXHViMTI0XHVjNjI0XHVjNzU4IFx1YWNhOVx1Yzc5MFx1ZDMxMFx1Yzc0NCBcdWM3NzRcdWI5YWNcdWM4MDBcdWI5YWMgXHVjMGI0XHVkM2I0XHViY2Y0XHVjNTU4XHViMmU0LiBcdWM1YmNcdWI5YzggXHViNGE0LCBcdWQ1NThcdWIwOThcdWM3NTggXHVhY2E5XHVjNzkwXHViOTdjIFx1YjIwNFx1Yjk3NFx1YWM4YyBcdWI0MThcdWJhNzQgXHVjNzkwXHVjMmUwXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU3NCBcdWFkZjggXHVhY2E5XHVjNzkwXHVjNjQwIFx1YzVmMFx1YWNiMFx1YjQxYyBcdWJhYThcdWI0ZTAgXHVjZTc4XHViNGU0XHVjNzU4IFx1YzBjOVx1Yzc3NCBcdWJjMThcdWM4MDRcdWI0MWNcdWIyZTRcdWIyOTQgXHVjMGFjXHVjMmU0XHVjNzQ0IFx1YWQwMFx1Y2MzMFx1ZDU2MCBcdWMyMTggXHVjNzg4XHVjNWM4XHViMmU0LiBcdWM1ZWNcdWFlMzBcdWMxMWMsIFx1YjQ1MCBcdWFjYTlcdWM3OTBcdWFjMDAgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWM4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0MCBcdWI0NTAgXHVhY2E5XHVjNzkwIFx1YzBhY1x1Yzc3NFx1Yjk3YyBcdWMxMWNcdWI4NWMgXHVhYzE5XHVjNzQwIFx1YzBjOVx1Yzc3NFx1YmE3NFx1YzExYyBcdWJjYzBcdWM3NDQgXHVhY2Y1XHVjNzIwXHVkNTU4XHViMjk0IFx1YWNhOVx1Yzc5MFx1YjRlNFx1Yjg1Y1x1YjljYyBcdWM3NzRcdWIzZDlcdWQ1NThcdWM1ZWMgXHVjNjI0XHVhYzA4IFx1YzIxOCBcdWM3ODhcdWIyZTRcdWIyOTQgXHVhYzgzXHVjNzQ0IFx1YjczYlx1ZDU1Y1x1YjJlNC4gXHVjOWQxXHVjNzNjXHViODVjIFx1YjNjY1x1YzU0NFx1YzYyOCBcdWIxMjRcdWM2MjRcdWIyOTQgXHVkNTA0XHViODVjXHViM2M0XHVhYzAwIFx1YWNhOVx1Yzc5MFx1ZDMxMFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWI5N2MgXHViYzE0XHVhZmQ0XHViYzg0XHViODM4XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0NCBcdWM1NGNcdWFjZTAgXHVjODhjXHVjODA4XHVkNTg4XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHVjZDVjXHVjODg1IFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWM1NGNcdWFjZTAgXHVjNzg4XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCwgXHVjZDA4XHVhZTMwIFx1YzBjMVx1ZDBkY1x1Yjk3YyBcdWNkOTRcdWNlMjFcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1Yzc0NCBcdWFjODNcdWM3NzRcdWI3N2NcdWIyOTQgXHVkNzZjXHViOWRkXHVjNzQ0IFx1YWMwMFx1YzljMFx1YWUzMFx1Yjg1YyBcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1ZDUwNFx1Yjg1Y1x1YjNjNFx1YjI5NCBcdWFjYTlcdWM3OTBcdWQzMTBcdWM3NDQgMFx1YmM4OCBcdWM3NzRcdWMwYzEgXHViMjBjXHViODAwXHViMmU0KFx1YzU0NFx1YzljMSBcdWQ1NWMgXHViYzg4XHViM2M0IFx1YjIwNFx1Yjk3NFx1YzljMCBcdWM1NGFcdWM3NDAgXHVjMGMxXHVkMGRjXHVjNzdjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQpLiBcdWQ2MDRcdWM3YWMgXHVhYzAxIFx1YWNhOVx1Yzc5MFx1Yzc1OCBcdWMwYzlcdWFlNTRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhY2E5XHVjNzkwXHVkMzEwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWI4NWMgXHVhYzAwXHViMmE1XHVkNTVjIFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgMSwwMDAsMDAwLDAwNygxMDxzdXA+OTxcL3N1cD4gKyA3KVx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YzVlY1x1Yjc3Yy4gXHViNDUwIFx1YWNhOVx1Yzc5MFx1ZDMxMFx1Yzc1OCBcdWMwYzFcdWQwZGNcdWFjMDAgXHViMmU0XHViOTc0XHViMmU0XHViMjk0IFx1YWM4M1x1Yzc0MCwgXHVhYzE5XHVjNzQwIFx1YzcwNFx1Y2U1OFx1Yzc1OCBcdWFjYTlcdWM3OTBcdWM3NTggXHVjMGM5XHVjNzc0IFx1YjJlNFx1Yjk3OCBcdWFjYmRcdWM2YjBcdWFjMDAgXHVjODc0XHVjN2FjXHVkNTYwIFx1YjU0Y1x1Yjg1YyBcdWM4MTVcdWM3NThcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHVjOTA0XHVjNWQwIFx1YWNhOVx1Yzc5MFx1ZDMxMFx1Yzc1OCBcdWQ1ODlcdWM3NTggXHVjMjE4IDxlbT5OIDxcL2VtPlx1YWNmYyBcdWM1ZjRcdWM3NTggXHVjMjE4IDxlbT5NIDxcL2VtPlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgPGVtPk48XC9lbT4sIDxlbT5NPFwvZW0+ICZsZTsgMiwwMDApPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgPGVtPk4gPFwvZW0+XHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVkNjA0XHVjN2FjIFx1YWMwMSBcdWFjYTlcdWM3OTBcdWM3NTggXHVjMGM5XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD48ZW0+TiA8XC9lbT5cdWFjMWNcdWM3NTggXHVjOTA0IFx1YzkxMVx1YzVkMFx1YzExYyA8ZW0+aSA8XC9lbT5cdWJjODhcdWM5ZjggXHVjOTA0XHVjNzU4IDxlbT5qIDxcL2VtPlx1YmM4OFx1YzlmOCBcdWJiMzhcdWM3OTBcdWIyOTQgPGVtPmkgPFwvZW0+XHVkNTg5IDxlbT5qIDxcL2VtPlx1YzVmNCBcdWFjYTlcdWM3OTBcdWM3NTggXHVjMGM5XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YmE3MCwgJiMzOTs8Y29kZT5CPFwvY29kZT4mIzM5O1x1Yzc3OCBcdWFjYmRcdWM2YjAgXHVhYzgwXHVjNzQwXHVjMGM5LCAmIzM5Ozxjb2RlPlc8XC9jb2RlPiYjMzk7XHVjNzc4IFx1YWNiZFx1YzZiMCBcdWQ3NzBcdWMwYzlcdWM3ODRcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYiBcdWM5MDRcdWM1ZDAgXHVhY2E5XHVjNzkwXHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWMwYzFcdWQwZGNcdWI4NWMgXHVhYzAwXHViMmE1XHVkNTVjIFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgMSwwMDAsMDAwLDAwNygxMDxzdXA+OTxcL3N1cD4gKyA3KVx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4iLCJzYW1wbGVfZXhwbGFpbl8xIjoiPHByZT5cclxuPGNvZGU+V0I8XC9jb2RlPlxyXG48Y29kZT5CQjxcL2NvZGU+XHJcblxyXG48Y29kZT5XQjxcL2NvZGU+XHJcbjxjb2RlPkJXPFwvY29kZT48XC9wcmU+XHJcblxyXG48cD5cdWM3NzRcdWI4MDdcdWFjOGMgXHViNDUwIFx1YWMwMFx1YzljMFx1YWMwMCBcdWFjMDBcdWIyYTVcdWQ1NThcdWIyZTQuPFwvcD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMTU5OTkiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSZXZlcnNpbmciLCJkZXNjcmlwdGlvbiI6IjxwPkNvbnNpZGVyIGEgcmVjdGFuZ3VsYXIgZ3JpZCBvZiBzaXplICROIFxcdGltZXMgTSQuIEVhY2ggY2VsbCBpcyBjb2xvcmVkIGJsYWNrIG9yIHdoaXRlLjxcL3A+XHJcblxyXG48cD5JZiB5b3UgdG91Y2ggYSBjZWxsICRDJCBvZiB0aGUgZ3JpZCwgeW91IGNoYW5nZSB0aGUgY29sb3Igb2YgYWxsIHRoZSBjZWxscyB0aGF0IGJlbG9uZyB0byBzYW1lLWNvbG9yZWQgY29ubmVjdGVkIGNvbXBvbmVudCBvZiAkQyQsIGluY2x1ZGluZyAkQyQgaXRzZWxmLiBGb3IgY29ubmVjdGVkIGNvbXBvbmVudHMsIHR3byBjZWxscyBhcmUgbmVpZ2hib3JzIGlmIHRoZXkgc2hhcmUgYSBzaWRlLjxcL3A+XHJcblxyXG48cD5Zb3Uga25vdyB0aGUgY3VycmVudCBzdGF0ZSBvZiB0aGUgZ3JpZCwgYnV0IHlvdSBtYXkgaGF2ZSB0b3VjaGVkIHNvbWUgY2VsbHMgYW4gYXJiaXRyYXJ5IG51bWJlciBvZiB0aW1lcy4gQ2FsY3VsYXRlIHRoZSBudW1iZXIgb2YgcG9zc2libGUgaW5pdGlhbCBzdGF0ZXMgb2YgdGhlIGdyaWQuIEFzIHRoZSBhbnN3ZXIgbWF5IGJlIHZlcnkgbGFyZ2UsIGNhbGN1bGF0ZSBpdCBtb2R1bG8gJDFcXCwwMDBcXCwwMDBcXCwwMDckLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgY29udGFpbnMgdHdvIGludGVnZXJzICROJCBhbmQgJE0kLCB0aGUgZGltZW5zaW9ucyBvZiB0aGUgZ3JpZCAoJDEgXFxsZSBOLCBNIFxcbGUgMjAwMCQpLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0ICROJCBsaW5lcyBkZXNjcmliZXMgb25lIHJvdyBvZiB0aGUgZ3JpZC4gRWFjaCBvZiB0aGVzZSBsaW5lcyBjb250YWlucyAkTSQgY2hhcmFjdGVycyBkZW5vdGluZyB0aGUgY29sb3JzIG9mIGNlbGxzIGluIHRoZSByb3cuIEVhY2ggY2hhcmFjdGVyIGlzIGVpdGhlciAmcXVvdDs8Y29kZT5CPFwvY29kZT4mcXVvdDsmbmJzcDtmb3IgYmxhY2sgb3IgJnF1b3Q7PGNvZGU+VzxcL2NvZGU+JnF1b3Q7Jm5ic3A7Zm9yIHdoaXRlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlByaW50IHRoZSBudW1iZXIgb2YgcG9zc2libGUgaW5pdGlhbCBzdGF0ZXMgb2YgdGhlIGdyaWQgbW9kdWxvICQxXFwsMDAwXFwsMDAwXFwsMDA3JC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d