Palindrome Path 3

Time limit1sMemory limit256 MB

Summary

Count the paths from the top-left to the bottom-right corner moving only right or down whose letters form a palindrome, modulo 1000000007.

Level: Medium7 of 10
Topics: Dynamic programming, Matrix
Solved: No attempts yet

Problem

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$ .

Input

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

Output

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

Note

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

Examples4

Example 1
Input
```
4
ABCD
BXZX
CDXB
WCBA
```
Expected output
```
12
```
Example 2
Input
```
2
AA
AA
```
Expected output
```
2
```
Example 3
Input
```
3
ABC
DEF
GHI
```
Expected output
```
0
```
Example 4
Input
```
2
AB
CD
```
Expected output
```
0
```