Percorsi Palindromici (Gold)#11174

Percorsi Palindromici (Gold)

2 secondi

128 megabyte

Difficile

La fattoria di Farmer John è una griglia di campi $n \times n$ n \times n, dove ogni campo contiene una lettera dell'alfabeto. Per esempio:

ABCD
BXZX
CDXB
WCBA

Ogni giorno, la mucca Bessie cammina dal campo in alto a sinistra al campo in basso a destra. A ogni passo, si muove di un campo verso destra oppure di un campo verso il basso. Mentre cammina, Bessie registra la stringa formata dalle lettere dei campi che visita.

Tuttavia, Bessie diventa molto confusa se la stringa risultante è un palindromo (cioè, se si legge allo stesso modo in avanti e all'indietro), perché non riesce più a ricordare in quale direzione ha camminato.

Aiuta Bessie a determinare il numero di percorsi distinti che producono una stringa palindroma. Percorsi diversi che producono lo stesso palindromo devono essere contati separatamente.

Stampa la risposta modulo $1 0^{9} + 7$ 10^9 + 7.

Input

La prima riga contiene un intero $n (1 \leq n \leq 500)$ n~(1 \le n \le 500).

Le successive $n$ righe contengono le $n$ righe della griglia. Ogni riga è composta da $n$ lettere maiuscole da A a Z.

Output

Stampa il numero di percorsi dal campo in alto a sinistra al campo in basso a destra la cui stringa risultante è un palindromo, modulo $1 0^{9} + 7$ 10^9 + 7.

Esempi

Bessie può ottenere i seguenti palindromi:

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

Esempio 1