Задача: Palindromic Paths
<div>Ферма Джона представлена решёткой <strong>N×N</strong> полей (1≤N≤500). Каждое поле представлено символом латинского алфавита. Например:</div> <div>ABCD</div> <div>BXZX</div> <div>CDXB</div> <div>WCBA</div> <div>Каждый день корова Беси прогуливается из верхнего левого угла в правый нижний, каждый раз двигаясь на один шаг вправо или вниз. Беси записывает в строку буквы, по которым прошлась. Она огорчится, если у неё получится палиндром (слово, которое читается одинаково слева направо и справа налево), поскольку тогда она запутается, в каком направлении двигалась.</div> <div> </div> <div>Пожалуйста, помогите Беси определить количество различных маршрутов которыми она может получить палиндромы. Различные пути, которыми получаются одинаковые палиндромы учитывать множество раз. Выведите свой ответ по модулю 1,000,000,007.</div> <div> </div> <div><strong>ФОРМАТ ВВОДА</strong>:</div> <div>Первая строка ввода содержит N, и последующие N строк содержат N строк решётки, описывающей поля. Каждая строка содержит N символов в интервале A..Z.<br /> <div><strong>ФОРМАТ ВЫВОДА</strong>:</div> <div>Выведите количество различных путей Беси, формирующих палиндромы по модулю 1,000,000,007.</div> <table border="1" cellpadding="1" cellspacing="1" style="width: 500px"> <tbody> <tr> <td>Ввод</td> <td>Вывод</td> </tr> <tr> <td> <div>4</div> <div>ABCD</div> <div>BXZX</div> <div>CDXB</div> <div>WCBA</div> </td> <td>12</td> </tr> </tbody> </table> </div> Примечание: <div>Беси может сделать следующие палиндромы:</div> <div> </div> <div>1 x "ABCDCBA"</div> <div>1 x "ABCWCBA"</div> <div>6 x "ABXZXBA"</div> <div>4 x "ABXDXBA"</div>
Ваш ответ: