Палиндромические пути

Задана квадратная таблица размером n × n, заполненная натуральными числами. Рассмотрим пути, которые начинаются в левой верхней ячейке таблицы и заканчиваются в правой нижней, двигаясь только вправо или вниз (но не влево или вверх). Каждый такой путь включает 2n - 1 число. Если последовательность чисел вдоль пути читается одинаково в обоих направлениях, то такой путь называется палиндромическим.

Задание

Определите общее количество палиндромических путей в данной таблице.

Входные данные

Первая строка входного файла содержит размер таблицы — целое число n: 2 ≤ n ≤ 100. В следующих n строках записаны по n натуральных чисел, не превышающих 10 000, которые составляют таблицу.

Выходные данные

Выходной файл должен содержать одно число: остаток от деления количества палиндромических путей на 101.

Комментарий

В первом примере существует четыре палиндромических пути:

1. вправо — вправо — вниз — вниз (7–10–5–10–7);

2. вправо — вниз — вправо — вниз (7–10–8–10–7);

3. вниз — вправо — вниз — вправо (7–5–8–5–7);

4. вниз — вниз — вправо — вправо (7–5–8–5–7).

Во втором примере все 252 возможных пути являются палиндромическими, поэтому необходимо вывести остаток от деления 252 на 101, что равно 50.

Примеры