회문 경로

땅은 N×N 필드(1≤N≤500)의 격자 형태로 되어 있으며, 각 필드는 알파벳으로 표시됩니다. 예를 들면:

ABCD
BXZX
CDXB
WCBA

매일, 강아지는 왼쪽 상단의 필드에서 오른쪽 하단의 필드로 걸어갑니다. 각 걸음마다 그녀는 오른쪽이나 아래쪽으로 한 필드씩 움직입니다. 강아지는 이 과정에서 건너가는 글자로 문자열을 생성하는 것을 기록하고 있습니다. 그러나 이 문자열이 회문(앞으로 읽으나 뒤로 읽으나 동일한 문자열)이 되면 매우 방향 감각을 잃게 됩니다, 왜냐하면 그녀는 어느 방향으로 갔는지 헷갈리게 되기 때문입니다.

강아지가 회문에 해당하는 고유한 경로의 수를 결정하는 데 도움을 주십시오. 동일한 회문을 얻는 다른 방법은 여러 번 계산됩니다. 답변을 1,000,000,007로 나눈 나머지를 출력해주세요.
 

입력의 첫 번째 줄에는 N이 포함되어 있으며, 나머지 N 줄에는 필드의 격자 N 행이 포함됩니다. 각 행에는 A..Z 범위의 N개의 문자가 포함됩니다.

강아지가 선택할 수 있는 고유한 회문 경로의 수를 출력해주세요, 이 때 1,000,000,007로 나눈 나머지 값을 출력합니다.