eolymp
bolt
Try our new interface for solving problems
Məsələlər

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

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

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

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

Завдання

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

Giriş verilənləri

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

Çıxış verilənləri

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

Nümunə

Giriş verilənləri #1
3
7 10 5
5 8 10
8 5 7
Çıxış verilənləri #1
4
Giriş verilənləri #2
6
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
1 1 1 1 1 1
Çıxış verilənləri #2
50

Qeyd

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

  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.