팰린드롬 경로 3

$N \times N$ 농장 ($1 \leq N \leq 500$) 각 칸에 대문자가 적혀 있다. 송아지는 $(1,1)$에서 $(N,N)$까지 오른쪽 또는 아래로만 이동한다. 경로에 적힌 글자열이 팰린드롬이면 길을 잃는다. 팰린드롬 경로의 개수를 $1{,}000{,}000{,}007$로 나눈 나머지를 구하라.

첫 줄에 $N$, 다음 $N$줄에 격자가 주어진다.

팰린드롬 경로의 개수를 $1{,}000{,}000{,}007$로 나눈 나머지를 출력한다.

예제 $4 \times 4$ 격자의 답은 $12$이다.