시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB37191463.636%

문제

상근이는 N행 N열로 이루어진 모눈종이를 구매했다. 모눈종이는 가장 처음에 모든 칸이 흰 색이다. 상근이는 이 칸 중 일부를 검정색으로 칠하려고 한다.

모눈종이의 경계선을 따라서 붙어있는 칸을 선택한다면, 직사각형을 만들 수 있다. 그리고 그 직사각형 내부의 색이 모두 검정색이고, 크기가 두 칸 이상이라면, 이 직사각형을 검정 직사각형이라고 한다.

왼쪽에서 선택한 직사각형은 모두 검정 직사각형이 아니다. 1번 직사각형은 내부의 색 중 한 칸이 흰색이고, 2번은 한 칸이기 때문에 검정 직사각형이 아니다. 오른쪽 그림에서 선택한 세 개 직사각형은 모두 검정 직사각형이다.

이렇게 상근이가 적절히 색칠한 모눈종이가 주어졌을 때, 겹치는 칸이 없게 검정 직사각형 두 개를 선택하는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. (2 ≤ N ≤ 1000) 다음 줄부터 N개 줄에는 각 모눈종이 칸의 색이 주어진다. C는 검정색, B는 흰색을 의미한다.

출력

첫째 줄에 겹치는 칸이 없게 두 검정 직사각형을 선택하는 방법의 수를 10007로 나눈 나머지 값을 출력한다.

예제 입력 1

2
CC
CC

예제 출력 1

2

예제 입력 2

3
CCB
CCB
CBB

예제 출력 2

5

예제 입력 3

5
BCCBB
BBCBB
BCCBB
BBBBB
CCBBB

예제 출력 3

8
W3sicHJvYmxlbV9pZCI6IjI4NzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjODBcdWM4MTUgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgTlx1ZDU4OSBOXHVjNWY0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJhYThcdWIyMDhcdWM4ODVcdWM3NzRcdWI5N2MgXHVhZDZjXHViOWU0XHVkNTg4XHViMmU0LiBcdWJhYThcdWIyMDhcdWM4ODVcdWM3NzRcdWIyOTQgXHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWJhYThcdWI0ZTAgXHVjZTc4XHVjNzc0IFx1ZDc3MCBcdWMwYzlcdWM3NzRcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzQgXHVjZTc4IFx1YzkxMSBcdWM3N2NcdWJkODBcdWI5N2MgXHVhYzgwXHVjODE1XHVjMGM5XHVjNzNjXHViODVjIFx1Y2U2MFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjIwOFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWFjYmRcdWFjYzRcdWMxMjBcdWM3NDQgXHViNTMwXHViNzdjXHVjMTFjIFx1YmQ5OVx1YzViNFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTVjXHViMmU0XHViYTc0LCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFkZjggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YjBiNFx1YmQ4MFx1Yzc1OCBcdWMwYzlcdWM3NzQgXHViYWE4XHViNDUwIFx1YWM4MFx1YzgxNVx1YzBjOVx1Yzc3NFx1YWNlMCwgXHVkMDZjXHVhZTMwXHVhYzAwIFx1YjQ1MCBcdWNlNzggXHVjNzc0XHVjMGMxXHVjNzc0XHViNzdjXHViYTc0LCBcdWM3NzQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YWM4MFx1YzgxNSBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2VhZmFmZDM3LTc1ZTItNDhlOS1hMTdhLWY4ODY4Yjc0MzBmM1wvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogMzk3cHg7IGhlaWdodDogMTYycHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzY3Y1x1Y2FiZFx1YzVkMFx1YzExYyBcdWMxMjBcdWQwZGRcdWQ1NWMgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWFjODBcdWM4MTUgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4gMVx1YmM4OCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHViMGI0XHViZDgwXHVjNzU4IFx1YzBjOSBcdWM5MTEgXHVkNTVjIFx1Y2U3OFx1Yzc3NCBcdWQ3NzBcdWMwYzlcdWM3NzRcdWFjZTAsIDJcdWJjODhcdWM3NDAgXHVkNTVjIFx1Y2U3OFx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVhYzgwXHVjODE1IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc3NCBcdWM1NDRcdWIyYzhcdWIyZTQuIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWM1ZDBcdWMxMWMgXHVjMTIwXHVkMGRkXHVkNTVjIFx1YzEzOCBcdWFjMWMgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWFjODBcdWM4MTUgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI4MDdcdWFjOGMgXHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1YzgwMVx1YzgwOFx1ZDc4OCBcdWMwYzlcdWNlNjBcdWQ1NWMgXHViYWE4XHViMjA4XHVjODg1XHVjNzc0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWNiOVx1Y2U1OFx1YjI5NCBcdWNlNzhcdWM3NzQgXHVjNWM2XHVhYzhjIFx1YWM4MFx1YzgxNSBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTUgXHViNDUwIFx1YWMxY1x1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWIyOTQgXHViYzI5XHViYzk1XHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDEwMDApIFx1YjJlNFx1Yzc0YyBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YmFhOFx1YjIwOFx1Yzg4NVx1Yzc3NCBcdWNlNzhcdWM3NTggXHVjMGM5XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gQ1x1YjI5NCBcdWFjODBcdWM4MTVcdWMwYzksIEJcdWIyOTQgXHVkNzcwXHVjMGM5XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWNiOVx1Y2U1OFx1YjI5NCBcdWNlNzhcdWM3NzQgXHVjNWM2XHVhYzhjIFx1YjQ1MCBcdWFjODBcdWM4MTUgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIDEwMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzAgXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyODc0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ1JOSSIsImRlc2NyaXB0aW9uIjoiPHA+RXZlbiB0aG91Z2ggaGUgaGFzIGZvdW5kIGFsbCB0aGUgbW9zdCBhbXVzaW5nIHJpZGVzLCBNaXJrbyZyc3F1bztzIGVudGh1c2lhc20gc3RpbGwgaXNuJnJzcXVvO3QgZmFkaW5nLiBIZSBvcGVuZWQgaGlzIGdyYXBoIHBhcGVyIG5vdGVib29rIGFuZCBzdGFydGVkIGNvbG91cmluZyBzcXVhcmVzLCBhbmQgYSBuZXcsIGV2ZW4gaGFyZGVyIHByb2JsZW0gZGF3bmVkIG9uIGhpbS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+WW91IGFyZSBnaXZlbiBhIHNxdWFyZSB0YWJsZSBjb25zaXN0aW5nIG9mIE4gcm93cyBieSBOIGNvbHVtbnMuIEVhY2ggY2VsbCBpcyBlaXRoZXIgYmxhY2sgb3Igd2hpdGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkEgc2V0IG9mIGNlbGxzIGZvcm1pbmcgYSByZWN0YW5nbGUsIHdpdGggaG9yaXpvbnRhbCBhbmQgdmVydGljYWwgZWRnZXMgZm9sbG93aW5nIGNlbGwgYm9yZGVycywgc2hhbGwgYmUgY2FsbGVkIGEgYmxhY2sgcmVjdGFuZ2xlIGlmIGFsbCBjZWxscyBpbnNpZGUgdGhlIHJlY3RhbmdsZSBhcmUgYmxhY2sgYW5kIGl0IGNvbnNpc3RzIG9mIGF0IGxlYXN0IHR3byBjZWxscy48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9lYWZhZmQzNy03NWUyLTQ4ZTktYTE3YS1mODg2OGI3NDMwZjNcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDM5N3B4OyBoZWlnaHQ6IDE2MnB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgbGVmdCBpbWFnZSBzaG93cyB0d28gcmVjdGFuZ2xlcyB3aGljaCBhcmUgbm90IGJsYWNrIHJlY3RhbmdsZXMuIFRoZSByZWN0YW5nbGUgbGFiZWxsZWQgMSBpcyBub3QgYSBibGFjayByZWN0YW5nbGUgYmVjYXVzZSBpdCBjb250YWlucyBhIHdoaXRlIGNlbGwsIGFuZCB0aGUgcmVjdGFuZ2xlIGxhYmVsbGVkIDIgaXMgbm90IGEgYmxhY2sgcmVjdGFuZ2xlIGJlY2F1c2UgaXQgY29uc2lzdHMgb2Ygb25seSBvbmUgY2VsbC4gT24gdGhlIG90aGVyIGhhbmQsIHRoZSByaWdodCBpbWFnZSBzaG93cyB0aHJlZSB2YWxpZCBibGFjayByZWN0YW5nbGVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5DYWxjdWxhdGUgdGhlIG51bWJlciBvZiBwb3NzaWJsZSBzZWxlY3Rpb25zIG9mIHR3byBibGFjayByZWN0YW5nbGVzIHRoYXQgaGF2ZSBubyBjb21tb24gY2VsbHMuIEFzIHRoZSByZXF1aXJlZCBudW1iZXIgY2FuIGJlIGV4dHJlbWVseSBsYXJnZSwgeW91IHNob3VsZCBvdXRwdXQgdGhlIHJlbWFpbmRlciBvZiBkaXZpZGluZyB0aGF0IG51bWJlciBieSAxMCAwMDcuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICgyICZsZTsgTiAmbGU7IDEwMDApLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IE4gbGluZXMgY29udGFpbnMgYSBzaW5nbGUgcm93IG9mIHRoZSB0YWJsZSwgY29uc2lzdGluZyBvZiBOIHN5bWJvbHMuIFRoZSBzeW1ib2wgJiMzOTtDJiMzOTsgcmVwcmVzZW50cyBhIGJsYWNrIGNlbGwsIHdoaWxlICYjMzk7QiYjMzk7IHJlcHJlc2VudHMgYSB3aGl0ZSBjZWxsLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBtdXN0IGNvbnRhaW4gdGhlIHJlbWFpbmRlciBvZiBkaXZpZGluZyB0aGUgcmVxdWlyZWQgbnVtYmVyIGJ5IDEwMDA3LjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2010/2011 > Contest #2 6번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: rhs0266