회문 경로

농장은 $N \times N$ 크기의 격자이고 ($2 \le N \le 18$), 각 칸에는 A부터 Z까지의 대문자가 하나씩 적혀 있다.

소 베시는 매일 왼쪽 위 칸에서 출발해 오른쪽 아래 칸까지 걸어간다. 한 번 움직일 때마다 오른쪽으로 한 칸 또는 아래로 한 칸 이동한다. 출발 칸과 도착 칸을 포함해 지나간 칸의 글자를 순서대로 읽으므로, 한 번의 산책은 길이 $2N-1$인 문자열 하나를 만든다.

이 문자열이 회문이면 베시는 방향 감각을 잃는다. 회문은 앞에서 읽으나 뒤에서 읽으나 같아서 자신이 어느 쪽으로 걸었는지 헷갈리기 때문이다.

베시가 만들 수 있는 회문의 개수를 구하라. 서로 다른 경로가 같은 회문을 만들면 한 번만 센다.

다음 격자를 보자.

ABCD
BXZX
CDXB
WCBA

ABXZXBA를 만드는 경로는 여러 개지만, 베시가 만들 수 있는 회문은 ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA 네 개뿐이다.

첫째 줄에 $N$이 주어진다. 다음 $N$개 줄에는 격자의 한 행씩이 주어지며, 각 줄은 A부터 Z까지의 문자 $N$개로 이루어져 있다.

베시가 만들 수 있는 서로 다른 회문의 개수를 출력한다.