Ферма Джона представлена решёткой из
\(N \times N\) полей(\(2 \le N \le 18\)), каждое из которых помечено буквой алфавита. Например,
ABCD
BXZX
CDXB
WCBA
Каждый день корова Беси идёт с левого верхнего угла в правый нижний, двигаясь либо на одну клетку вправо, либо на одну клетку вниз. Беси записывает строку, которая получается в результате её маршрута, построенную из букв, по которым она прошла. Он будет очень расстроена, если в результате построенная строка окажется палиндромом (читается одинаково от начала к концу и от конца к началу), поскольку она запутается в каком направлении она шла.
Пожалуйста, помогите Беси определить количество различных палиндромов, которые она сможет сформировать во время своего путешествия. Различные способы формировать один и тот же палиндром следует учитывать только один раз. Например, в примере выше имеется несколько способов сформировать палиндром ABXZXBA, однако существует всего 4 различных палиндрома, которые Беси может сформировать
ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.
ФОРМАТ ВВОДА (файл palpath.in):
Первая строка ввода содержит \(N\), а последующие
\(N\) строк содержат \(N\) описание поля. Каждая строка содержит по \(N\) символов в диапазоне A..Z.
ФОРМАТ ВЫВОДА (файл palpath.out):
Выведите количество различных палиндромов, которые Беси может сформировать.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
ABCD
BXZX
CDXB
WCBA
|
4
|