【问题描述】
FJ的农场是一个N*N格子形状的一块地（2<N<18）， 每个格子用一个字母表示，比如：
ABCD
BXZX
CDXB
WCBA

每天，Bessie奶牛从左上角走向右下角，她每一步可以向右或向下走。 Bessie记录着她走的过程中所产生的字符串。 她的方向感很差，所以生成出来的字符串要是回文串（从前和从后读是一样的）， 因为她不记得她曾经走过的方向。
  帮Bessie她可以走出的不同的回文串的个数。沿不同路径走出的相同的回文串只算一次。比如说，上面的例子中有多种不同的路径可以产生出回文串ABXZXBA，但Bessie只能走出四种不同的回文串：ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA 。

输入格式：（palpath.in）
第一行包括一个整数N，剩下的N行每行包括N个在A-Z之间的字符，表示这块农场。

输出格式：（palpath.out）
输出Bessie可能走出的不同的回文串的个数。

Sample 1

Input

4
ABCD
BXZX
CDXB
WCBA

Output

4

Limitation

1s, 128MiB for each test case.