Паліндромні шляхи (Золото)#11174

Паліндромні шляхи (Золото)

2 секунди

128 мегабайтів

Складна

Ферма Фермера Джона являє собою сітку полів розміром $n \times n$ n \times n, де кожне поле містить літеру алфавіту. Наприклад:

ABCD
BXZX
CDXB
WCBA

Кожного дня корова Бессі йде від верхнього лівого поля до нижнього правого поля. На кожному кроці вона рухається або на одне поле праворуч, або на одне поле вниз. Під час ходьби Бессі записує рядок, утворений літерами полів, які вона відвідала.

Однак Бессі дуже плутається, якщо отриманий рядок є паліндромом (тобто якщо він читається однаково зліва направо і справа наліво), оскільки вона більше не може пригадати, в якому напрямку йшла.

Будь ласка, допоможіть Бессі визначити кількість різних маршрутів, які утворюють рядок-паліндром. Різні маршрути, що утворюють один і той самий паліндром, слід рахувати окремо.

Виведіть відповідь за модулем $1 0^{9} + 7$ 10^9 + 7.

Вхідні дані

Перший рядок містить ціле число $n (1 \leq n \leq 500)$ n~(1 \le n \le 500).

Наступні $n$ рядків містять $n$ рядків сітки. Кожен рядок складається з $n$ великих літер від A до Z.

Вихідні дані

Виведіть кількість маршрутів від верхнього лівого поля до нижнього правого поля, отриманий рядок яких є паліндромом, за модулем $1 0^{9} + 7$ 10^9 + 7.

Приклади

Бессі може утворити такі паліндроми:

1 x "ABCDCBA"
1 x "ABCWCBA"
6 x "ABXZXBA"
4 x "ABXDXBA"

Приклад 1