题目描述

农夫约翰的农场呈N×N的网格状（2≤N≤18），每个格子都标有一个字母。例如：

ABCD
BXZX
CDXB
WCBA

每天，奶牛贝西从左上角的格子走到右下角的格子，每一步她要么向右走一格，要么向下走一格。贝西会记录她在这个过程中生成的字符串，该字符串由她走过的格子上的字母组成。然而，如果这个字符串是一个回文（正读和反读都一样），她会感到非常困惑，因为她会搞不清自己走的方向。

请帮助贝西确定她在行走过程中可以形成的不同回文的数量。形成相同回文的不同方式只算一次；例如，上面的例子中有几条路线可以产生回文ABXZXBA，但贝西总共只能形成4个不同的回文：ABCDCBA、ABCWCBA、ABXZXBA、ABXDXBA。

输入格式

• 第一行输入包含N，接下来的N行包含网格的N行。每行包含N个字符，范围在A..Z之间。

输出格式

• 输出贝西可以形成的不同回文的数量。

样例

样例输入

4
ABCD
BXZX
CDXB
WCBA

样例输出

4

数据范围

2≤N≤18，网格中的字符为A..Z的大写字母