USACO 2015 US Open, Gold
Problem 2. Palindromic Paths
Contest has ended.
Log in to allow submissions in analysis mode
Ферма Джона представлена решёткой $N \times N$ полей ($1 \le N \le 500$).
Каждое поле представлено символом латинского алфавита. Например:
Contest has ended. No further submissions allowed.
ABCD BXZX CDXB WCBA
Каждый день корова Беси прогуливается из верхнего левого угла в правый нижний, каждый раз двигаясь на один шаг вправо или вниз. Беси записывает в строку буквы, по которым прошлась. Она огорчится, если у неё получится палиндром (слово, которое читается одинаково слева направо и справа налево), поскольку тогда она запутается, в каком направлении двигалась.
Пожалуйста, помогите Беси определить количество различных маршрутов которыми она может получить палиндромы. Различные пути, которыми получаются одинаковые палиндромы учитывать множество раз. Выведите свой ответ по модулю 1,000,000,007.
ФОРМАТ ВЫВОДА (файл palpath.in):
Первая строка ввода содержит $N$, и последующие $N$ строк содержат $N$ строк решётки, описывающей поля. Каждая строка содержит $N$ символов в интервале A..Z.ФОРМАТ ВЫВОДА (файл palpath.out):
Выведите количество различных путей Беси, формирующих палиндромы по модулю 1,000,000,007.ПРИМЕР ВВОДА:
4 ABCD BXZX CDXB WCBA
ПРИМЕР ВЫВОДА:
12
Беси может сделать следующие палиндромы:
- 1 x "ABCDCBA"
- 1 x "ABCWCBA"
- 6 x "ABXZXBA"
- 4 x "ABXDXBA"