Description

FJ的农场是一个N*N格子形状的一块地（2<N<18）， 每个格子用一个字母表示，比如：

ABCD

BXZX

CDXB

WCBA

每天，Bessie奶牛从左上角走向右下角，她每一步可以向右或向下走。 Bessie记录着她走的过程中所产生的字符串。 她的方向感很差，所以生成出来的字符串要是回文串（从前和从后读是一样的）， 因为她不记得她曾经走过的方向。

帮Bessie她可以走出的不同的回文串的个数。沿不同路径走出的相同的回文串只算一次。比如说，上面的例子中有多种不同的路径可以产生出回文串ABXZXBA，但Bessie只能走出四种不同的回文串：ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA 。

Input Format

第一行包括一个整数N，剩下的N行每行包括N个在A-Z之间的字符，表示这块农场。

Output Format

输出Bessie可能走出的不同的回文串的个数。

Sample

输入样例： 4 ABCD BXZX CDXB WCBA 输出样例： 4