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