시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 32 17 12 60.000%

문제

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

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

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

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

입력

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

출력

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

예제 입력 1

5
BCCBB
BBCBB
BCCBB
BBBBB
CCBBB

예제 출력 1

8
W3sicHJvYmxlbV9pZCI6IjI4NzQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjODBcdWM4MTUgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgTlx1ZDU4OSBOXHVjNWY0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWJhYThcdWIyMDhcdWM4ODVcdWM3NzRcdWI5N2MgXHVhZDZjXHViOWU0XHVkNTg4XHViMmU0LiBcdWJhYThcdWIyMDhcdWM4ODVcdWM3NzRcdWIyOTQgXHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWJhYThcdWI0ZTAgXHVjZTc4XHVjNzc0IFx1ZDc3MCBcdWMwYzlcdWM3NzRcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3NzQgXHVjZTc4IFx1YzkxMSBcdWM3N2NcdWJkODBcdWI5N2MgXHVhYzgwXHVjODE1XHVjMGM5XHVjNzNjXHViODVjIFx1Y2U2MFx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjIwOFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWFjYmRcdWFjYzRcdWMxMjBcdWM3NDQgXHViNTMwXHViNzdjXHVjMTFjIFx1YmQ5OVx1YzViNFx1Yzc4OFx1YjI5NCBcdWNlNzhcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTVjXHViMmU0XHViYTc0LCBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YWRmOFx1YjlhY1x1YWNlMCBcdWFkZjggXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1IFx1YjBiNFx1YmQ4MFx1Yzc1OCBcdWMwYzlcdWM3NzQgXHViYWE4XHViNDUwIFx1YWM4MFx1YzgxNVx1YzBjOVx1Yzc3NFx1YWNlMCwgXHVkMDZjXHVhZTMwXHVhYzAwIFx1YjQ1MCBcdWNlNzggXHVjNzc0XHVjMGMxXHVjNzc0XHViNzdjXHViYTc0LCBcdWM3NzQgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzQ0IFx1YWM4MFx1YzgxNSBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JsYWNrcmVjdC5wbmdcIiBzdHlsZT1cIndpZHRoOiA0MTBweDsgaGVpZ2h0OiAxNzRweDtcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHViYWE4XHViNDUwIFx1YWM4MFx1YzgxNSBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzQgXHVjNTQ0XHViMmM4XHViMmU0LiAxXHViYzg4IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0MCBcdWIwYjRcdWJkODBcdWM3NTggXHVjMGM5IFx1YzkxMSBcdWQ1NWMgXHVjZTc4XHVjNzc0IFx1ZDc3MFx1YzBjOVx1Yzc3NFx1YWNlMCwgMlx1YmM4OFx1Yzc0MCBcdWQ1NWMgXHVjZTc4XHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWFjODBcdWM4MTUgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVjNjI0XHViOTc4XHVjYWJkIFx1YWRmOFx1YjliY1x1YzVkMFx1YzExYyBcdWMxMjBcdWQwZGRcdWQ1NWMgXHVjMTM4IFx1YWMxYyBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDAgXHViYWE4XHViNDUwIFx1YWM4MFx1YzgxNSBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjgwN1x1YWM4YyBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjODAxXHVjODA4XHVkNzg4IFx1YzBjOVx1Y2U2MFx1ZDU1YyBcdWJhYThcdWIyMDhcdWM4ODVcdWM3NzRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVhY2I5XHVjZTU4XHViMjk0IFx1Y2U3OFx1Yzc3NCBcdWM1YzZcdWFjOGMgXHVhYzgwXHVjODE1IFx1YzljMVx1YzBhY1x1YWMwMVx1ZDYxNSBcdWI0NTAgXHVhYzFjXHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU1OFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTAwMCkgXHViMmU0XHVjNzRjIFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHViYWE4XHViMjA4XHVjODg1XHVjNzc0IFx1Y2U3OFx1Yzc1OCBcdWMwYzlcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBDXHViMjk0IFx1YWM4MFx1YzgxNVx1YzBjOSwgQlx1YjI5NCBcdWQ3NzBcdWMwYzlcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVhY2I5XHVjZTU4XHViMjk0IFx1Y2U3OFx1Yzc3NCBcdWM1YzZcdWFjOGMgXHViNDUwIFx1YWM4MFx1YzgxNSBcdWM5YzFcdWMwYWNcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTU4XHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc1OCBcdWMyMThcdWI5N2MgMTAwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMCBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjI4NzQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDUk5JIiwiZGVzY3JpcHRpb24iOiI8cD5FdmVuIHRob3VnaCBoZSBoYXMgZm91bmQgYWxsIHRoZSBtb3N0IGFtdXNpbmcgcmlkZXMsIE1pcmtvJnJzcXVvO3MgZW50aHVzaWFzbSBzdGlsbCBpc24mcnNxdW87dCBmYWRpbmcuIEhlIG9wZW5lZCBoaXMgZ3JhcGggcGFwZXIgbm90ZWJvb2sgYW5kIHN0YXJ0ZWQgY29sb3VyaW5nIHNxdWFyZXMsIGFuZCBhIG5ldywgZXZlbiBoYXJkZXIgcHJvYmxlbSBkYXduZWQgb24gaGltLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Zb3UgYXJlIGdpdmVuIGEgc3F1YXJlIHRhYmxlIGNvbnNpc3Rpbmcgb2YgTiByb3dzIGJ5IE4gY29sdW1ucy4gRWFjaCBjZWxsIGlzIGVpdGhlciBibGFjayBvciB3aGl0ZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QSBzZXQgb2YgY2VsbHMgZm9ybWluZyBhIHJlY3RhbmdsZSwgd2l0aCBob3Jpem9udGFsIGFuZCB2ZXJ0aWNhbCBlZGdlcyBmb2xsb3dpbmcgY2VsbCBib3JkZXJzLCBzaGFsbCBiZSBjYWxsZWQgYSBibGFjayByZWN0YW5nbGUgaWYgYWxsIGNlbGxzIGluc2lkZSB0aGUgcmVjdGFuZ2xlIGFyZSBibGFjayBhbmQgaXQgY29uc2lzdHMgb2YgYXQgbGVhc3QgdHdvIGNlbGxzLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2JsYWNrcmVjdC5wbmdcIiBzdHlsZT1cImhlaWdodDoxNzRweDsgd2lkdGg6NDEwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIGxlZnQgaW1hZ2Ugc2hvd3MgdHdvIHJlY3RhbmdsZXMgd2hpY2ggYXJlIG5vdCBibGFjayByZWN0YW5nbGVzLiBUaGUgcmVjdGFuZ2xlIGxhYmVsbGVkIDEgaXMgbm90IGEgYmxhY2sgcmVjdGFuZ2xlIGJlY2F1c2UgaXQgY29udGFpbnMgYSB3aGl0ZSBjZWxsLCBhbmQgdGhlIHJlY3RhbmdsZSBsYWJlbGxlZCAyIGlzIG5vdCBhIGJsYWNrIHJlY3RhbmdsZSBiZWNhdXNlIGl0IGNvbnNpc3RzIG9mIG9ubHkgb25lIGNlbGwuIE9uIHRoZSBvdGhlciBoYW5kLCB0aGUgcmlnaHQgaW1hZ2Ugc2hvd3MgdGhyZWUgdmFsaWQgYmxhY2sgcmVjdGFuZ2xlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Q2FsY3VsYXRlIHRoZSBudW1iZXIgb2YgcG9zc2libGUgc2VsZWN0aW9ucyBvZiB0d28gYmxhY2sgcmVjdGFuZ2xlcyB0aGF0IGhhdmUgbm8gY29tbW9uIGNlbGxzLiBBcyB0aGUgcmVxdWlyZWQgbnVtYmVyIGNhbiBiZSBleHRyZW1lbHkgbGFyZ2UsIHlvdSBzaG91bGQgb3V0cHV0IHRoZSByZW1haW5kZXIgb2YgZGl2aWRpbmcgdGhhdCBudW1iZXIgYnkgMTAgMDA3LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdGhlIGludGVnZXIgTiAoMiAmbGU7IE4gJmxlOyAxMDAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBOIGxpbmVzIGNvbnRhaW5zIGEgc2luZ2xlIHJvdyBvZiB0aGUgdGFibGUsIGNvbnNpc3Rpbmcgb2YgTiBzeW1ib2xzLiBUaGUgc3ltYm9sICYjMzk7QyYjMzk7IHJlcHJlc2VudHMgYSBibGFjayBjZWxsLCB3aGlsZSAmIzM5O0ImIzM5OyByZXByZXNlbnRzIGEgd2hpdGUgY2VsbC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgZmlyc3QgYW5kIG9ubHkgbGluZSBvZiBvdXRwdXQgbXVzdCBjb250YWluIHRoZSByZW1haW5kZXIgb2YgZGl2aWRpbmcgdGhlIHJlcXVpcmVkIG51bWJlciBieSAxMDAwNy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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