문제

ANA 동아리방은 $N \times N$ 크기의 격자 형태로 되어 있다. ($2 \le N \le 18$) 격자의 각 칸에는 알파벳 대문자가 하나씩 적혀 있다.

진원이는 매일 격자의 왼쪽 맨 위 칸에서 출발하여 오른쪽 맨 아래 칸까지 이동한다. 이동할 때는 한 번에 오른쪽으로 한 칸 또는 아래쪽으로 한 칸만 움직일 수 있다. 진원이는 이동하면서 지나온 칸들에 적힌 문자를 순서대로 이어 붙여 문자열을 만든다. 만약 이 문자열이 앞뒤가 똑같은 팰린드롬(Palindrome)이라면, 진원이는 자신이 어느 방향으로 걸어왔는지 헷갈려 어지러움을 느낀다.

진원이가 이동 경로를 통해 만들 수 있는 서로 다른 팰린드롬 문자열의 개수를 구하시오. 같은 팰린드롬 문자열을 만드는 서로 다른 경로가 여러 개 있더라도, 해당 문자열은 한 번만 센다. 예를 들어, 아래와 같은 격자에서 ABXZXBA라는 팰린드롬을 만드는 경로는 여러 가지가 있지만, 진원이가 만들 수 있는 서로 다른 팰린드롬은 ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA로 총 4가지뿐이다.

ABCD
BXZX
CDXB
WCBA

입력

첫째 줄에 격자의 크기 $N$이 주어진다. ($2 \le N \le 18$)

이어서 $N$개의 줄에 격자의 각 행을 나타내는 $N$개의 문자가 주어진다. 각 문자는 알파벳 대문자 A부터 Z 사이 중 하나이다.

출력

진원이가 만들 수 있는 서로 다른 팰린드롬 문자열의 개수를 출력한다.

예제 입력 1

4
ABCD
BXZX
CDXB
WCBA

예제 출력 1

4