팰린드롬 경로

아케이드 게임은 N×N 크기의 격자판 (2≤N≤18) 형태로 이루어져 있으며, 각 칸마다 알파벳 한 글자가 적혀 있습니다. 예를 들면:

ABCD
BXZX
CDXB
WCBA

매일, 게이머 지민은 왼쪽 상단의 칸에서 시작하여 오른쪽 하단의 칸으로 이동합니다. 그녀는 한 번에 오른쪽 또는 아래로 한 칸씩만 움직일 수 있습니다. 이동하면서 지나가는 칸들의 알파벳으로 문자열을 만듭니다. 하지만, 이 문자열이 팰린드롬(앞에서 읽으나 뒤에서 읽으나 같은 문자열)이면 그녀는 혼란에 빠집니다.

지민이 움직이면서 만들 수 있는 서로 다른 팰린드롬의 수를 구해주세요. 동일한 팰린드롬을 만드는 다양한 경로는 한 번만 계산합니다. 예를 들어, 위의 격자판에서는 ABXZXBA와 같은 팰린드롬을 만드는 여러 경로가 있지만, 지민이 만들 수 있는 서로 다른 팰린드롬은 ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA의 네 가지뿐입니다.

입력의 첫 번째 줄에는 N이 주어지고, 그 다음 N개의 줄에는 격자판의 N개의 행이 주어집니다. 각 행에는 N개의 A..Z 범위의 문자가 포함됩니다.

지민이 만들 수 있는 서로 다른 팰린드롬의 수를 출력해주세요.