Ферма Джона представлена решёткой N×N полей (1≤N≤500). Каждое поле представлено символом латинского алфавита. Например:
ABCD
BXZX
CDXB
WCBA
Каждый день корова Беси прогуливается из верхнего левого угла в правый нижний, каждый раз двигаясь на один шаг вправо или вниз. Беси записывает в строку буквы, по которым прошлась. Она огорчится, если у неё получится палиндром (слово, которое читается одинаково слева направо и справа налево), поскольку тогда она запутается, в каком направлении двигалась.
Пожалуйста, помогите Беси определить количество различных маршрутов которыми она может получить палиндромы. Различные пути, которыми получаются одинаковые палиндромы учитывать множество раз. Выведите свой ответ по модулю 1,000,000,007.
ФОРМАТ ВВОДА:
Первая строка ввода содержит N, и последующие N строк содержат N строк решётки, описывающей поля. Каждая строка содержит N символов в интервале A..Z.
ФОРМАТ ВЫВОДА:
Выведите количество различных путей Беси, формирующих палиндромы по модулю 1,000,000,007.
| Ввод |
Вывод |
|
4
ABCD
BXZX
CDXB
WCBA
|
12 |
Примечание:
Беси может сделать следующие палиндромы:
1 x "ABCDCBA"
1 x "ABCWCBA"
6 x "ABXZXBA"
4 x "ABXDXBA"