문제

이안이가 활동하는 동아리방은 $N \times N$ ($1 \le N \le 500$) 크기의 격자 모양으로 되어 있다. 격자의 각 칸에는 알파벳 대문자가 하나씩 적혀 있다. 예를 들면 다음과 같다.

ABCD
BXZX
CDXB
WCBA

이안이는 매일 격자의 왼쪽 위 칸 $(1, 1)$에서 출발하여 오른쪽 아래 칸 $(N, N)$까지 이동한다. 이안이는 한 번에 오른쪽 또는 아래쪽으로만 한 칸씩 이동할 수 있다. 이안이는 이동하면서 지나온 칸에 적힌 문자들을 순서대로 이어 붙여 문자열을 만든다. 그런데 만약 이 문자열이 앞에서부터 읽으나 뒤에서부터 읽으나 같은 회문(palindrome)이라면, 이안이는 자신이 어느 방향으로 걸어왔는지 헷갈려 방향 감각을 잃고 만다.

이안이가 이동할 수 있는 경로 중, 만들어진 문자열이 회문이 되는 서로 다른 경로의 수를 구하는 프로그램을 작성하시오. 같은 문자열을 만들더라도 경로가 다르면 서로 다른 경로로 계산한다. 결과값이 매우 커질 수 있으므로, $1\,000\,000\,007$로 나눈 나머지를 출력한다.

입력

첫째 줄에 격자의 크기 $N$이 주어진다. ($1 \le N \le 500$)

다음 $N$개의 줄에는 격자의 각 행을 나타내는 $N$개의 문자가 공백 없이 주어진다. 모든 문자는 알파벳 대문자 A부터 Z 사이이다.

출력

이안이가 택할 수 있는 서로 다른 회문 경로의 수를 $1\,000\,000\,007$로 나눈 나머지를 출력한다.

예제 입력 1

4
ABCD
BXZX
CDXB
WCBA

예제 출력 1

12