Farmer John's Palindromic Paths

Farmer John's farm is in the shape of an \(N \times N\) grid of fields (\(1 \le N \le 500\)), each labeled with an uppercase letter. Each day, Bessie the cow walks from the upper-left field to the lower-right field. At each step, she may move one field to the right or one field downward. As she walks, she forms a string from the letters she visits. However, if this string is a palindrome (reads the same forward and backward), Bessie becomes disoriented. Your task is to compute the number of distinct routes Bessie can take which result in a palindromic string. Note that different paths that yield the same palindrome are counted separately. Output your answer modulo \(10^9+7\).

inputFormat

The first line contains an integer \(N\), the size of the grid. The following \(N\) lines each contain a string of \(N\) uppercase letters representing the grid.

outputFormat

Output a single integer: the number of palindromic routes modulo \(10^9+7\).

sample

2
AA
AA

2