시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 235 80 64 35.955%

문제

N * N 크기의 격자모양의 농장이 있다. (1≤N≤500). 격자의 간 칸들에는 알파벳이 한글자씩 쓰여 있다. 예를 들어 아래와 같은 식이다 (N=4)

ABCD
BXZX
CDXB
WCBA

농장에 사는 귀여운 송아지가 한마리 있는데, 이 송아지가 지금 농장의 왼쪽 위 (1,1)에서 출발하여 엄마소가 있는 곳(N,N)으로 가려고 한다. 송아지는 엄마가 너무 보고 싶기 때문에 오른쪽 또는 아래로만 움직인다. 송아지는 아직 어려서 길을 잘 모른다. 그래서 바닥에 쓰여진 알파벳을 보고 길을 찾아간다. 하지만 만약에 송아지가 출발점에서 도착점까지 가면서 만들게 되는 경로가 팰린드롬이라면 앞뒤를 구분하지 못해서 길을 잃어버린다.

귀여운 송아지가 길을 잃지않고 엄마소를 찾을 수 있도록 1,1 에서 출발하여 N,N까지 가는 경로 중 팰린드롬인 경로의 개수를 계산하여 알려주자.

답이 커질 수 있으므로 1,000,000,007로 나눈 나머지를 출력한다.

입력

첫 번째 줄에 격자의 크기 N이 주어지고, 두번재 줄 ~ N+1번째 줄에 걸쳐 농장에 쓰여진 알파벳이 주어진다. 알파벳은 대문자로만 이루어져 있다.

출력

1,1에서 N,N으로 가는 경로 중 팰린드롬인 경로의 개수를 1,000,000,007로 나눈 나머지를 출력하라.

예제 입력 1

4
ABCD
BXZX
CDXB
WCBA

예제 출력 1

12

힌트

위 예제에서 만들 수 있는 팰린드롬은 아래와 같다.

  • 1 x "ABCDCBA"
  • 1 x "ABCWCBA"
  • 6 x "ABXZXBA"
  • 4 x "ABXDXBA"

1 + 1 + 6 + 4 = 12

W3sicHJvYmxlbV9pZCI6IjEwNzU5IiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVkMzMwXHViOWIwXHViNGRjXHViODZjIFx1YWNiZFx1Yjg1YyAzIiwiZGVzY3JpcHRpb24iOiI8cD5OICogTiBcdWQwNmNcdWFlMzBcdWM3NTggXHVhY2E5XHVjNzkwXHViYWE4XHVjNTkxXHVjNzU4IFx1YjE4ZFx1YzdhNVx1Yzc3NCBcdWM3ODhcdWIyZTQuICgxJmxlO04mbGU7NTAwKS4gXHVhY2E5XHVjNzkwXHVjNzU4IFx1YWMwNCBcdWNlNzhcdWI0ZTRcdWM1ZDBcdWIyOTQgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzc0IFx1ZDU1Y1x1YWUwMFx1Yzc5MFx1YzUyOSBcdWM0ZjBcdWM1ZWMgXHVjNzg4XHViMmU0LiBcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NDAgXHVjMmRkXHVjNzc0XHViMmU0IChOPTQpPFwvcD5cclxuXHJcbjxwcmU+XHJcbkFCQ0RcclxuQlhaWFxyXG5DRFhCXHJcbldDQkE8XC9wcmU+XHJcblxyXG48cD5cdWIxOGRcdWM3YTVcdWM1ZDAgXHVjMGFjXHViMjk0IFx1YWRjMFx1YzVlY1x1YzZiNCBcdWMxYTFcdWM1NDRcdWM5YzBcdWFjMDAgXHVkNTVjXHViOWM4XHViOWFjIFx1Yzc4OFx1YjI5NFx1YjM3MCwgXHVjNzc0IFx1YzFhMVx1YzU0NFx1YzljMFx1YWMwMCBcdWM5YzBcdWFlMDggXHViMThkXHVjN2E1XHVjNzU4IFx1YzY3Y1x1Y2FiZCBcdWM3MDQgKDEsMSlcdWM1ZDBcdWMxMWMgXHVjZDljXHViYzFjXHVkNTU4XHVjNWVjIFx1YzVjNFx1YjljOFx1YzE4Y1x1YWMwMCBcdWM3ODhcdWIyOTQgXHVhY2YzKE4sTilcdWM3M2NcdWI4NWMgXHVhYzAwXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjMWExXHVjNTQ0XHVjOWMwXHViMjk0IFx1YzVjNFx1YjljOFx1YWMwMCBcdWIxMDhcdWJiMzQgXHViY2Y0XHVhY2UwIFx1YzJmNlx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAgXHVjNjI0XHViOTc4XHVjYWJkIFx1YjYxMFx1YjI5NCBcdWM1NDRcdWI3OThcdWI4NWNcdWI5Y2MgXHVjNmMwXHVjOWMxXHVjNzc4XHViMmU0LiBcdWMxYTFcdWM1NDRcdWM5YzBcdWIyOTQgXHVjNTQ0XHVjOWMxIFx1YzViNFx1YjgyNFx1YzExYyBcdWFlMzhcdWM3NDQgXHVjNzk4IFx1YmFhOFx1Yjk3OFx1YjJlNC4gXHVhZGY4XHViNzk4XHVjMTFjIFx1YmMxNFx1YjJlNVx1YzVkMCBcdWM0ZjBcdWM1ZWNcdWM5YzQgXHVjNTRjXHVkMzBjXHViY2IzXHVjNzQ0IFx1YmNmNFx1YWNlMCBcdWFlMzhcdWM3NDQgXHVjYzNlXHVjNTQ0XHVhYzA0XHViMmU0LiBcdWQ1NThcdWM5YzBcdWI5Y2MgXHViOWNjXHVjNTdkXHVjNWQwIFx1YzFhMVx1YzU0NFx1YzljMFx1YWMwMCBcdWNkOWNcdWJjMWNcdWM4MTBcdWM1ZDBcdWMxMWMgXHViM2M0XHVjYzI5XHVjODEwXHVhZTRjXHVjOWMwIFx1YWMwMFx1YmE3NFx1YzExYyBcdWI5Y2NcdWI0ZTRcdWFjOGMgXHViNDE4XHViMjk0IFx1YWNiZFx1Yjg1Y1x1YWMwMCBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzRcdWI3N2NcdWJhNzQgXHVjNTVlXHViNGE0XHViOTdjIFx1YWQ2Y1x1YmQ4NFx1ZDU1OFx1YzljMCBcdWJhYmJcdWQ1NzRcdWMxMWMgXHVhZTM4XHVjNzQ0IFx1Yzc4M1x1YzViNFx1YmM4NFx1YjliMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhZGMwXHVjNWVjXHVjNmI0IFx1YzFhMVx1YzU0NFx1YzljMFx1YWMwMCBcdWFlMzhcdWM3NDQgXHVjNzgzXHVjOWMwXHVjNTRhXHVhY2UwIFx1YzVjNFx1YjljOFx1YzE4Y1x1Yjk3YyBcdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjNjNFx1Yjg1ZCAxLDEgXHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU1OFx1YzVlYyBOLE5cdWFlNGNcdWM5YzAgXHVhYzAwXHViMjk0IFx1YWNiZFx1Yjg1YyBcdWM5MTEgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzc4IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHVjNWVjIFx1YzU0Y1x1YjgyNFx1YzhmY1x1Yzc5MC48XC9wPlxyXG5cclxuPHA+XHViMmY1XHVjNzc0IFx1Y2VlNFx1YzljOCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYmMwXHViODVjIDEsMDAwLDAwMCwwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjYTlcdWM3OTBcdWM3NTggXHVkMDZjXHVhZTMwIE5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWMwXHVhY2UwLCBcdWI0NTBcdWJjODhcdWM3YWMgXHVjOTA0IH4gTisxXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHViMThkXHVjN2E1XHVjNWQwIFx1YzRmMFx1YzVlY1x1YzljNCBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM1NGNcdWQzMGNcdWJjYjNcdWM3NDAgXHViMzAwXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+MSwxXHVjNWQwXHVjMTFjIE4sTlx1YzczY1x1Yjg1YyBcdWFjMDBcdWIyOTQgXHVhY2JkXHViODVjIFx1YzkxMSBcdWQzMzBcdWI5YjBcdWI0ZGNcdWI4NmNcdWM3NzggXHVhY2JkXHViODVjXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyAxLDAwMCwwMDAsMDA3XHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViNzdjLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM3MDQgXHVjNjA4XHVjODFjXHVjNWQwXHVjMTFjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMjk0IFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc0MCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPjEgeCAmcXVvdDtBQkNEQ0JBJnF1b3Q7PFwvbGk+XHJcblx0PGxpPjEgeCAmcXVvdDtBQkNXQ0JBJnF1b3Q7PFwvbGk+XHJcblx0PGxpPjYgeCAmcXVvdDtBQlhaWEJBJnF1b3Q7PFwvbGk+XHJcblx0PGxpPjQgeCAmcXVvdDtBQlhEWEJBJnF1b3Q7PFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+MSArIDEgKyA2ICsgNCA9IDEyPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIxMDc1OSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlBhbGluZHJvbWljIFBhdGhzIiwiZGVzY3JpcHRpb24iOiI8cD5GYXJtZXIgSm9obiYjMzk7cyBmYXJtIGlzIGluIHRoZSBzaGFwZSBvZiBhbiBOJnRpbWVzO04gZ3JpZCBvZiBmaWVsZHMgKDEmbGU7TiZsZTs1MDApLCBlYWNoIGxhYmVsZWQgd2l0aCBhIGxldHRlciBpbiB0aGUgYWxwaGFiZXQuIEZvciBleGFtcGxlOjxcL3A+XHJcblxyXG48cHJlPlxyXG5BQkNEXHJcbkJYWlhcclxuQ0RYQlxyXG5XQ0JBPFwvcHJlPlxyXG5cclxuPHA+RWFjaCBkYXksIEJlc3NpZSB0aGUgY293IHdhbGtzIGZyb20gdGhlIHVwcGVyLWxlZnQgZmllbGQgdG8gdGhlIGxvd2VyLXJpZ2h0IGZpZWxkLCBlYWNoIHN0ZXAgdGFraW5nIGhlciBlaXRoZXIgb25lIGZpZWxkIHRvIHRoZSByaWdodCBvciBvbmUgZmllbGQgZG93bndhcmQuIEJlc3NpZSBrZWVwcyB0cmFjayBvZiB0aGUgc3RyaW5nIHRoYXQgc2hlIGdlbmVyYXRlcyBkdXJpbmcgdGhpcyBwcm9jZXNzLCBidWlsdCBmcm9tIHRoZSBsZXR0ZXJzIHNoZSB3YWxrcyBhY3Jvc3MuIFNoZSBnZXRzIHZlcnkgZGlzb3JpZW50ZWQsIGhvd2V2ZXIsIGlmIHRoaXMgc3RyaW5nIGlzIGEgcGFsaW5kcm9tZSAocmVhZGluZyB0aGUgc2FtZSBmb3J3YXJkIGFzIGJhY2t3YXJkKSwgc2luY2Ugc2hlIGdldHMgY29uZnVzZWQgYWJvdXQgd2hpY2ggZGlyZWN0aW9uIHNoZSBoYWQgd2Fsa2VkLjxcL3A+XHJcblxyXG48cD5QbGVhc2UgaGVscCBCZXNzaWUgZGV0ZXJtaW5lIHRoZSBudW1iZXIgb2YgZGlzdGluY3Qgcm91dGVzIHNoZSBjYW4gdGFrZSB0aGF0IGNvcnJlc3BvbmQgdG8gcGFsaW5kcm9tZXMuIERpZmZlcmVudCB3YXlzIG9mIG9idGFpbmluZyB0aGUgc2FtZSBwYWxpbmRyb21lIGNvdW50IG11bHRpcGxlIHRpbWVzLiBQbGVhc2UgcHJpbnQgeW91ciBhbnN3ZXIgbW9kdWxvIDEsMDAwLDAwMCwwMDcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBOLCBhbmQgdGhlIHJlbWFpbmluZyBOIGxpbmVzIGNvbnRhaW4gdGhlIE4gcm93cyBvZiB0aGUgZ3JpZCBvZiBmaWVsZHMuIEVhY2ggcm93IGNvbnRhaW5zIE4gY2hhcmFjdGVycyB0aGF0IGFyZSBpbiB0aGUgcmFuZ2UgQS4uWi48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QbGVhc2Ugb3V0cHV0IHRoZSBudW1iZXIgb2YgZGlzdGluY3QgcGFsaW5kcm9taWMgcm91dGVzIEJlc3NpZSBjYW4gdGFrZSwgbW9kdWxvIDEsMDAwLDAwMCwwMDcuPFwvcD5cclxuIiwiaGludCI6IjxwPkJlc3NpZSBjYW4gbWFrZSB0aGUgZm9sbG93aW5nIHBhbGluZHJvbWVzPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSB4ICZxdW90O0FCQ0RDQkEmcXVvdDs8XC9saT5cclxuXHQ8bGk+MSB4ICZxdW90O0FCQ1dDQkEmcXVvdDs8XC9saT5cclxuXHQ8bGk+NiB4ICZxdW90O0FCWFpYQkEmcXVvdDs8XC9saT5cclxuXHQ8bGk+NCB4ICZxdW90O0FCWERYQkEmcXVvdDs8XC9saT5cclxuPFwvdWw+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d