시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 234 79 63 35.593%

문제

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+XHVhZGMwXHVjNWVjXHVjNmI0IFx1YzFhMVx1YzU0NFx1YzljMFx1YWMwMCBcdWFlMzhcdWM3NDQgXHVjNzgzXHVjOWMwXHVjNTRhXHVhY2UwIFx1YzVjNFx1YjljOFx1YzE4Y1x1Yjk3YyBcdWNjM2VcdWM3NDQgXHVjMjE4IFx1Yzc4OFx1YjNjNFx1Yjg1ZCAxLDEgXHVjNWQwXHVjMTFjIFx1Y2Q5Y1x1YmMxY1x1ZDU1OFx1YzVlYyBOLE5cdWFlNGNcdWM5YzAgXHVhYzAwXHViMjk0IFx1YWNiZFx1Yjg1YyBcdWM5MTEgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzc4IFx1YWNiZFx1Yjg1Y1x1Yzc1OCBcdWFjMmZcdWMyMThcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTU4XHVjNWVjIFx1YzU0Y1x1YjgyNFx1YzhmY1x1Yzc5MC48XC9wPlxyXG5cclxuPHA+XHViMmY1XHVjNzc0IFx1Y2VlNFx1YzljOCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYmMwXHViODVjIDEsMDAwLDAwMCwwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWNhOVx1Yzc5MFx1Yzc1OCBcdWQwNmNcdWFlMzAgTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWFjZTAsIFx1YjQ1MFx1YmM4OFx1YzdhYyBcdWM5MDQgfiBOKzFcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWM3OFx1Y2NkMCBcdWIxOGRcdWM3YTVcdWM1ZDAgXHVjNGYwXHVjNWVjXHVjOWM0IFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc0MCBcdWIzMDBcdWJiMzhcdWM3OTBcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD4xLDFcdWM1ZDBcdWMxMWMgTixOXHVjNzNjXHViODVjIFx1YWMwMFx1YjI5NCBcdWFjYmRcdWI4NWMgXHVjOTExIFx1ZDMzMFx1YjliMFx1YjRkY1x1Yjg2Y1x1Yzc3OCBcdWFjYmRcdWI4NWNcdWM3NTggXHVhYzJmXHVjMjE4XHViOTdjIDEsMDAwLDAwMCwwMDdcdWI4NWMgXHViMDk4XHViMjA4IFx1YjA5OFx1YmEzOFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NThcdWI3N2MuPFwvcD5cclxuIiwiaGludCI6IjxwPlx1YzcwNCBcdWM2MDhcdWM4MWNcdWM1ZDBcdWMxMWMgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyOTQgXHVkMzMwXHViOWIwXHViNGRjXHViODZjXHVjNzQwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MSB4ICZxdW90O0FCQ0RDQkEmcXVvdDs8XC9saT5cclxuXHQ8bGk+MSB4ICZxdW90O0FCQ1dDQkEmcXVvdDs8XC9saT5cclxuXHQ8bGk+NiB4ICZxdW90O0FCWFpYQkEmcXVvdDs8XC9saT5cclxuXHQ8bGk+NCB4ICZxdW90O0FCWERYQkEmcXVvdDs8XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD4xICsgMSArIDYgKyA0ID0gMTI8XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjEwNzU5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiUGFsaW5kcm9taWMgUGF0aHMiLCJkZXNjcmlwdGlvbiI6IjxwPkZhcm1lciBKb2huJiMzOTtzIGZhcm0gaXMgaW4gdGhlIHNoYXBlIG9mIGFuIE4mdGltZXM7TiBncmlkIG9mIGZpZWxkcyAoMSZsZTtOJmxlOzUwMCksIGVhY2ggbGFiZWxlZCB3aXRoIGEgbGV0dGVyIGluIHRoZSBhbHBoYWJldC4gRm9yIGV4YW1wbGU6PFwvcD5cclxuXHJcbjxwcmU+XHJcbkFCQ0RcclxuQlhaWFxyXG5DRFhCXHJcbldDQkE8XC9wcmU+XHJcblxyXG48cD5FYWNoIGRheSwgQmVzc2llIHRoZSBjb3cgd2Fsa3MgZnJvbSB0aGUgdXBwZXItbGVmdCBmaWVsZCB0byB0aGUgbG93ZXItcmlnaHQgZmllbGQsIGVhY2ggc3RlcCB0YWtpbmcgaGVyIGVpdGhlciBvbmUgZmllbGQgdG8gdGhlIHJpZ2h0IG9yIG9uZSBmaWVsZCBkb3dud2FyZC4gQmVzc2llIGtlZXBzIHRyYWNrIG9mIHRoZSBzdHJpbmcgdGhhdCBzaGUgZ2VuZXJhdGVzIGR1cmluZyB0aGlzIHByb2Nlc3MsIGJ1aWx0IGZyb20gdGhlIGxldHRlcnMgc2hlIHdhbGtzIGFjcm9zcy4gU2hlIGdldHMgdmVyeSBkaXNvcmllbnRlZCwgaG93ZXZlciwgaWYgdGhpcyBzdHJpbmcgaXMgYSBwYWxpbmRyb21lIChyZWFkaW5nIHRoZSBzYW1lIGZvcndhcmQgYXMgYmFja3dhcmQpLCBzaW5jZSBzaGUgZ2V0cyBjb25mdXNlZCBhYm91dCB3aGljaCBkaXJlY3Rpb24gc2hlIGhhZCB3YWxrZWQuPFwvcD5cclxuXHJcbjxwPlBsZWFzZSBoZWxwIEJlc3NpZSBkZXRlcm1pbmUgdGhlIG51bWJlciBvZiBkaXN0aW5jdCByb3V0ZXMgc2hlIGNhbiB0YWtlIHRoYXQgY29ycmVzcG9uZCB0byBwYWxpbmRyb21lcy4gRGlmZmVyZW50IHdheXMgb2Ygb2J0YWluaW5nIHRoZSBzYW1lIHBhbGluZHJvbWUgY291bnQgbXVsdGlwbGUgdGltZXMuIFBsZWFzZSBwcmludCB5b3VyIGFuc3dlciBtb2R1bG8gMSwwMDAsMDAwLDAwNy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIE4sIGFuZCB0aGUgcmVtYWluaW5nIE4gbGluZXMgY29udGFpbiB0aGUgTiByb3dzIG9mIHRoZSBncmlkIG9mIGZpZWxkcy4gRWFjaCByb3cgY29udGFpbnMgTiBjaGFyYWN0ZXJzIHRoYXQgYXJlIGluIHRoZSByYW5nZSBBLi5aLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBsZWFzZSBvdXRwdXQgdGhlIG51bWJlciBvZiBkaXN0aW5jdCBwYWxpbmRyb21pYyByb3V0ZXMgQmVzc2llIGNhbiB0YWtlLCBtb2R1bG8gMSwwMDAsMDAwLDAwNy48XC9wPlxyXG4iLCJoaW50IjoiPHA+QmVzc2llIGNhbiBtYWtlIHRoZSBmb2xsb3dpbmcgcGFsaW5kcm9tZXM8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4xIHggJnF1b3Q7QUJDRENCQSZxdW90OzxcL2xpPlxyXG5cdDxsaT4xIHggJnF1b3Q7QUJDV0NCQSZxdW90OzxcL2xpPlxyXG5cdDxsaT42IHggJnF1b3Q7QUJYWlhCQSZxdW90OzxcL2xpPlxyXG5cdDxsaT40IHggJnF1b3Q7QUJYRFhCQSZxdW90OzxcL2xpPlxyXG48XC91bD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=