Задача Palway. Задано квадратну таблицю n × n, що складається з натуральних чисел. Розглядатимемо шляхи з лівої верхньої комірки таблиці у праву нижню, які довільним чином ідуть по комірках таблиці праворуч та донизу (але ніколи ліворуч або вгору). Уздовж кожного такого шляху розташовано 2n - 1 число. Якщо для певного шляху даний набір чисел є «симетричним», тобто читається у зворотному порядку так само, як і у прямому, називатимемо вибраний шлях паліндромічним. За заданою таблицею встановіть загальну кількість на ній паліндромічних шляхів.
Технічні умови. Програма Palway читає з пристрою стандартного введення ціле число n (2 <= n <= 100) – розмір таблиці. У наступних n рядках файлу записано по n натуральних чисел, що не перевищують 10 000 та задають таблицю. Програма виводить на пристрій стандартного виведення єдине число - остачу від ділення на 101 кількості паліндромічних шляхів на заданій таблиці.
|
№ |
Введення |
Виведення |
|---|---|---|
|
1 |
3 |
4 |
|
2 |
6 |
50 |
Приклади
Коментар
У першому прикладі є чотири паліндромічних шляхи:
- праворуч — праворуч — донизу — донизу (7–10–5–10–7);
- праворуч — донизу — праворуч — донизу (7–10–8–10–7);
- донизу — праворуч — донизу — праворуч (7–5–8–5–7);
- донизу — донизу — праворуч — праворуч (7–5–8–5–7).
У другому прикладі кожен з 252 можливих шляхів є паліндромічним, тож за умовою слід вивести остачу від ділення 252 на 101 — число 50.