Palindrome Path 3

An $N \times N$ farm grid ($1 \leq N \leq 500$) contains uppercase letters. A calf starts at $(1,1)$ and moves only right or down to reach $(N,N)$. It gets lost whenever the letters on its path form a palindrome. Count how many palindrome paths exist, modulo $1{,}000{,}000{,}007$.

Line 1: $N$. Next $N$ lines: the grid rows.

Print the number of palindrome paths modulo $1{,}000{,}000{,}007$.

On the sample $4 \times 4$ grid the answer is $12$.