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로 나눈 나머지를 출력하라.

예제 입력

4
ABCD
BXZX
CDXB
WCBA

예제 출력

12

힌트

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

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

1 + 1 + 6 + 4 = 12