Паліндромні шляхи (бронза)
Ферма Джона представлена у вигляді сітки розміром n на n клітин, кожна з яких позначена літерою алфавіту. Наприклад:
ABCD BXZX CDXB WCBA
Щодня корова Бессі вирушає з лівого верхнього кута до правого нижнього, рухаючись або на одну клітинку вправо, або на одну клітинку вниз. Бессі записує рядок, що утворюється в результаті її маршруту, складаючи його з літер, через які вона пройшла. Вона буде дуже засмучена, якщо цей рядок виявиться паліндромом (тобто читається однаково зліва направо і справа наліво), оскільки це заплутає її щодо напрямку руху.
Будь ласка, допоможіть Бессі визначити кількість різних паліндромів, які вона може утворити під час своєї подорожі. Різні шляхи, що формують один і той самий паліндром, слід враховувати лише один раз. Наприклад, у наведеному вище прикладі є кілька способів утворити паліндром ABXZXBA, але існує всього 4 різних паліндроми, які Бессі може утворити: ABCDCBA, ABCWCBA, ABXZXBA, ABXDXBA.
Вхідні дані
Перша строка містить n (2 ≤ n ≤ 18), а наступні n строк описують поле. Кожна строка містить n символів у діапазоні від A до Z.
Вихідні дані
Виведіть кількість різних паліндромів, які Бессі може утворити.