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