Problem
A fazenda de John é representada por uma grade de N×N campos (2≤N≤18), cada um rotulado com uma letra do alfabeto. Por exemplo,
ABCD
BXZX
CDXB
WCBA
Todos os dias Besi, a vaca, vai do canto superior esquerdo para o canto inferior direito, movendo-se uma célula para a direita ou uma célula para baixo. Besi anota o fio resultante do seu percurso, construído a partir das letras que percorreu. Ela ficará muito chateada se a string resultante for um palíndromo (é a mesma do começo ao fim e do fim ao começo), porque ela ficará confusa em qual direção ela foi.
Por favor, ajude Besie a descobrir quantos palíndromos diferentes ela pode formar durante sua jornada. Formas diferentes de formar o mesmo palíndromo devem ser contadas apenas uma vez. Por exemplo, no exemplo acima, existem várias formas de formar o palíndromo ABXZXBA, mas existem apenas 4 palíndromos diferentes que o Besi pode formar ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.
FORMATO DE ENTRADA:
A primeira linha de entrada contém N e as subsequentes N linhas contêm N descrição do campo. Cada linha contém N caracteres no intervalo A..Z.
FORMATO DE SAÍDA:
Imprima o número de palíndromos distintos que Besi pode formar.
| Entrada |
Saída |
|
4
ABCD
BXZX
CDXB
WCBA
|
4 |