Паліндромічні шляхи#7826

Паліндромічні шляхи

1 секунда

64 мегабайти

Складна

Дано квадратну таблицю розміром $n \times n$ n \times n, що складається з натуральних чисел. Розглядаємо шляхи з лівої верхньої комірки таблиці у праву нижню, які йдуть по комірках таблиці лише праворуч і вниз (але ніколи ліворуч або вгору). Уздовж кожного такого шляху розташовано $2 n - 1$ 2n - 1 число. Якщо для певного шляху даний набір чисел є симетричним, тобто читається у зворотному порядку так само, як і у прямому, вибраний шлях називатимемо паліндромічним.

Завдання

За заданою таблицею встановіть загальну кількість на ній паліндромічних шляхів.

Вхідні дані

У першому рядку вхідного файлу вказано розмір таблиці — ціле число $n$ , $2 \leq n \leq 100$ 2 \leq n \leq 100. У наступних $n$ рядках задано по $n$ натуральних чисел, що не перевищують $10000$ , які задають таблицю.

Вихідні дані

Вихідний файл повинен містити єдине число: остачу від ділення на $101$ кількості паліндромічних шляхів на заданій таблиці.

Приклади

Приклад 1

Приклад 2

Примітка

У першому прикладі є чотири паліндромічних шляхи:

$1)$ праворуч — праворуч — униз — униз $(7 - 10 - 5 - 10 - 7)$ (7-10-5-10-7);

$2)$ праворуч — униз — праворуч — униз $(7 - 10 - 8 - 10 - 7)$ (7-10-8-10-7);

$3)$ униз — праворуч — униз — праворуч $(7 - 5 - 8 - 5 - 7)$ (7-5-8-5-7);

$4)$ униз — униз — праворуч — праворуч $(7 - 5 - 8 - 5 - 7)$ (7-5-8-5-7).

У другому прикладі кожен з $252$ можливих шляхів є паліндромічним, тож за умовою слід вивести остачу від ділення $252$ на $101$ — число $50$ .