Palindromic Paths (Gold)#11174

Palindromic Paths (Gold)

2 секунде

128 мегабајтова

Тешко

Farmer John's farm is an $n \times n$ n \times n grid of fields, with each field containing a letter from the alphabet. For example:

ABCD
BXZX
CDXB
WCBA

Each day, Bessie the cow walks from the upper-left field to the lower-right field. At each step, she moves either one field to the right or one field downward. As she walks, Bessie records the string formed by the letters of the fields she visits.

However, Bessie becomes very confused if the resulting string is a palindrome (that is, if it reads the same forward and backward), because she can no longer remember which direction she walked.

Please help Bessie determine the number of distinct routes that produce a palindromic string. Different routes that produce the same palindrome should be counted separately.

Print the answer modulo $1 0^{9} + 7$ 10^9 + 7.

Улаз

The first line contains an integer $n (1 \leq n \leq 500)$ n~(1 \le n \le 500).

The next $n$ lines contain the $n$ rows of the grid. Each row consists of $n$ uppercase letters from $A$ to $Z$ .

Излаз

Print the number of routes from the upper-left field to the lower-right field whose resulting string is a palindrome, modulo $1 0^{9} + 7$ 10^9 + 7.

Примери

Bessie can make the following palindromes:

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

Пример 1