Ферма Джона представлена решёткой n * n полей. Каждое поле представлено символом латинского алфавита. Например:
Каждый день корова Беси прогуливается из верхнего левого угла в правый нижний, каждый раз двигаясь на один шаг вправо или вниз. Беси записывает в строку буквы, по которым прошлась. Она огорчится, если у неё получится палиндром (слово, которое читается одинаково слева направо и справа налево), поскольку тогда она запутается, в каком направлении двигалась.
Помогите Беси определить количество различных маршрутов которыми она может получить палиндромы. Различные пути, которыми получаются одинаковые палиндромы учитывать множество раз. Выведите свой ответ по модулю 10^9
+ 7.
Первая строка содержит n (1 ≤ n ≤ 500), последующие n строк содержат n строк решётки, описывающей поля. Каждая строка содержит n символов в интервале A..Z.
Выведите количество различных путей Беси, формирующих палиндромы по модулю 10^9
+ 7.
Беси может сделать следующие палиндромы: